代码随想录算法训练营day60 || 42.接雨水

问题：42. 接雨水 - 力扣（LeetCode）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路：本题我用的是双指针的方法，首先明确在遍历高度时，其最大值可由该点的高度值乘以左右两边第一个比该点高度小的差值再减去1得到，即s=max(s,(rheight-lheight-1)*height[i])。可定义两个向量用来记录某点处左右两边第一个小于该点高度的小标，同时注意初始化的值避免进入死循环，具体代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2) return 0;
        int sum = 0;
        vector<int> lheight(height.size(),0);
        vector<int> rheight(height.size(),0);
        lheight[0] = height[0];
        for(int i = 1;i < height.size(); i++){
            lheight[i] = max(lheight[i-1],height[i]);
        }
        rheight[height.size()-1] = height[height.size()-1];
        for(int i = rheight.size()-2;i >= 0;i--){
            rheight[i] = max(rheight[i+1],height[i]);
        }
        for(int i = 0;i < height.size();i++){
            int h = min(rheight[i],lheight[i]) - height[i];
            if(h > 0) sum += h;
        
        }
            
        return sum;
    }
};

现在状态不好，暂时用双指针方法，晚上再看看单调栈。