【c++】【leetcode42】接雨水（动态规划、单调栈、双指针）

接雨水

每一根柱子头顶上能接多少雨水取=min（左边最高，右边最高）- 柱子本身的高度
因此只需要得到下标为i的柱子左边最高的left_max和右边最高的right_max的值就可以

• ans[i] = min(left_max[i],right_max[i]) - height[i]

如果是每一个柱子都去遍历寻找，时间复杂度是 O ( n 2 ) O(n^2) O(n2)，这里可以借助动态规划去保存已经寻找过的信息。

动态规划：

• 初始化： left_max[0] = height[0]; right_max[n-1] = height[n-1];
• 动态转移方程：
  • left_max[i] = max(left_max[i-1],height[i]);//从左往右
  • right_max[j] = max(right_max[j+1],height[j]);//从右往左

时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( n ) O(n) O(n)

class Solution {
public:
    int trap(vector& height) {
        int n = height.size();
        int ans = 0;
        int left_max[n],right_max[n];
        left_max[0] = height[0];//初始化
        right_max[n-1] = height[n-1];//初始化
        for(int i = 1,j = n - 2;i < n,j >= 0;++i,--j){
            left_max[i] = max(left_max[i-1],height[i]);//转移方程
            right_max[j] = max(right_max[j+1],height[j]);//转移方程
        }
        for(int i = 0;i < n;++i){
            ans += min(left_max[i],right_max[i]) - height[i];//计算每一步的结果
        }
        return ans;
    }
};

用单调栈去记录下标：
维护一个递减的栈，当遇到第一个大于栈顶的元素，此时去计算能接的雨水量。

时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( n ) O(n) O(n)

class Solution {
public:
    int trap(vector& height) {
        int n = height.size();
        stack s;
        s.push(0);
        int ans = 0;
        for(int i = 1;i < n;++i){
            while(!s.empty() && height[i] > height[s.top()]){
                int top = s.top();//当前顶部
                s.pop();
                if(s.empty())break;
                int left = s.top();//顶部的前一位，大于顶部
                int wid = i - left - 1;//要计算的宽度
                int hei = min(height[left],height[i]) - height[top];//要计算的高度
                ans += wid * hei;
            }
            s.push(i);
        }
        return ans;
    }
};

优化动态规划：
用left_max、right_max分别记录左右两边的最大值，每一个柱子可以接的水依旧是min(left_max[i],right_max[i]) - height[i]。

要解决的问题是：怎么样才能保证left_max、right_max分别代表左右两边的最大值？
不需要是最大值，我们只需要保证最大值里相对较小的那一个正确即可，因为左右两边我们只用到了较小那一个。

两个指针在同一轮里移动，会导致最后可能会跳过某个柱子，所以这里用了if-else

class Solution {
public:
    int trap(vector& height) {
        int n = height.size();
        int l = 0,r = n - 1;
        int left_max = height[0],right_max = height[n-1];
        int ans = 0;

        while(l < r){
            left_max = max(height[l],left_max);
            right_max = max(height[r],right_max);
            if(left_max <= right_max){
                ans += left_max - height[l];
                l++;
            }
            else{
                ans += right_max - height[r];
                r--;
            }
        }   
        return ans;
    }
};