sum
,是每一列雨水 f(i)
的和f(i)
又是每一列最多能接的雨水capable
, 与 该列的柱子高度 height[i]
的差capable
根据短板效应,属于 i 左边的最大值lheight
与 右边的最大值 rheight
的最小值所以综合一下得到 sum( min(lheght, rheight) - height[i] ) (1 < i < height.size()-1)
class Solution { public: int trap(vector<int>& height) { int sum = 0; // 遍历每一列 for(int i = 0; i < height.size(); i++) { // 跳过第一列和最后一列 if(i == 0 || i == height.size()-1) continue; // 用两个变量分别记录左右两侧的最大值 int lheight = 0; int rheight = 0; // 求左侧最大值 for(int j = 0; j < i; j++) { if(height[j] > lheight) lheight = height[j]; } // 求右侧最大值 for(int j = i+1; j < height.size(); j++) { if(height[j] > rheight) rheight = height[j]; } // 得到当前i列能接到的雨水 int cur = min(lheight, rheight) - height[i]; // 累加到sum中 if(cur > 0) sum += cur; } return sum; } };
与上种解法有所不同,此处利用两个 vector 容器记录对应每个 i 值的 lheight 和 rheight ,最后累积相加即可。
class Solution { public: int trap(vector<int>& height) { // 处理边界 if(height.size() <= 2) return 0; // 两个维护左右侧最大柱高的容器 vector<int> lmax(height.size(), 0); vector<int> rmax(height.size(), 0); int len = rmax.size(); // 先遍历一次记录左侧最大柱高的容器 lmax[0] = height[0]; for(int i = 1; i < len; i++) { lmax[i] = max(height[i], lmax[i-1]); } // 先遍历一次记录右侧最大柱高的容器 rmax[len - 1] = height[len - 1]; for(int i = len-2; i >= 0; i--) { rmax[i] = max(height[i], rmax[i+1]); } // 遍历全部,累计相加 int sum = 0; for(int i = 0; i < len; i++) { int cur = min(lmax[i], rmax[i]) - height[i]; if(cur > 0) sum += cur; } return sum; } };
参考了官方题解,解法非常巧妙。首先利用了动态规划的思想,从左往右遍历整个数组,并建立一个辅助数组v。
v[i - difference]
的内容来更新v[i]
的值。arr = [ 1,2,4,3,5,8,7,5,1 ],difference = 2 可以手动测试一下,就知道这一句话实现了什么内容
class Solution { public: int longestSubsequence(vector<int> &arr, int difference) { int res = 0; // 此处辅助数组的建立要多加注意! unordered_map<int, int> map; for(auto i : arr) { map[i] = map[i-difference] + 1; res = max(res, map[i]); } return res; } };
关于辅助数组的建立:
由于上述代码的关键句会涉及到访问未初始化的数组成员,因此如果用:
vector<int> v
来接收和计算此题,一定会报错!
而 map 使用 [] 符号取值时,当 key 不存在时,c++ 会利用该 key 及默认构造的 value,组成一个{key, value}
对,插入 map 中,即将该 key 对应的 value 初始化为 0,所以访问不存在的元素时不会出错。