LeetCode[42] 接雨水

动态规划

1. left_max[i] = height[i]左侧的最高高度
2. right_max[i] = height[i]右侧的最高高度
3. height[i]能接多少水？min(left_max[i], right_max[i])-height[i]

class Solution {
public:int trap(vector<int>& height) {int len = height.size();vector<int> left_max(len,0);  // 左侧最高高度vector<int> right_max(len,0); // 右侧最高高度// 遍历获取左侧最高高度left_max[0] = height[0];for(int i=1;i<len;i++){left_max[i] = max(left_max[i-1],height[i]);}// 遍历获取右侧最高高度right_max[len-1] = height[len-1];for(int i=len-2;i>=0;i--){right_max[i] = max(right_max[i+1],height[i]);}// 获取接水量int res = 0;for(int i=0;i<len;i++){res += (min(left_max[i], right_max[i]) - height[i]);}return res;}
};

4. 优化：左侧最高高度可以只使用一个int变量，遍历获取接水量时动态更新

class Solution {
public:int trap(vector<int>& height) {int len = height.size();int left_max = 0;vector<int> right_max(len,0);right_max[len-1] = height[len-1];for(int i=len-2;i>=0;i--){right_max[i] = max(right_max[i+1],height[i]);}int res = 0;for(int i=0;i<len;i++){left_max = max(left_max, height[i]);res += (min(left_max, right_max[i]) - height[i]);}return res;}
};

双指针

1. 动态规划优化后依然需要维护左侧或者右侧的最高值，空间开销为O(n)
2. 使用左右指针动态维护左侧和右侧最高值

class Solution {
public:int trap(vector<int>& height) {int res = 0;int left = 0;int right = height.size()-1;int left_max = 0;int right_max = 0;while(left<=right){// 当前位置接的水 =（先前最高值 - 当前位置的高度）// 当左指针的最高高度大于等于右指针最高高度，计算右指针的接水量// 当右指针的最高高度大于左指针最高高度，计算左指针的接水量// 原因：另一侧比当前一侧高，所以当前位置条件满足时肯定能接到水if(left_max<=right_max){left_max = max(left_max,height[left]);res = res + left_max - height[left++];}else{right_max = max(right_max,height[right]);res = res + right_max - height[right--];}}return res;}
};

栈

1. 从左到右遍历数组，遍历到下标 i 时
2. 如果栈内至少有两个元素，记栈顶元素为 top
3. top 的下面一个元素是 left，则一定有 height[left]≥height[top]
4. 如果 height[i]>height[top]，则得到一个可以接雨水的区域
   • 该区域的宽度是 i−left−1
   • 高度是 min(height[left],height[i])−height[top]
   • 根据宽度和高度即可计算得到该区域能接的雨水量
5. 在对 top 计算能接的雨水量之后，left 变成新的 top，重复上述操作
6. 直到栈变为空，或者栈顶下标对应的 height 中的元素大于或等于 height[i]

class Solution {
public:int trap(vector<int>& height) {stack<int> mystack;int res = 0;for(int i=0; i<height.size(); i++){while (!mystack.empty() && height[i] > height[mystack.top()]) {int top = mystack.top();mystack.pop();if(mystack.empty()) break; // 例如第一个高度是0，没有左侧边界，是接不到水的int left = mystack.top();int curr_width = i - left - 1;int curr_height = min(height[left], height[i]) - height[top];res += curr_height*curr_width;}mystack.push(i);}return res;}
};