leetcode42. 接雨水

分析

暴力(超时）

class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        int size = height.size();
        for (int i = 1; i < size - 1; i++) {
        int max_left = 0, max_right = 0;
        for (int j = i; j >= 0; j--) { //查找左边最大值
            max_left = max(max_left, height[j]);
        }
        for (int j = i; j < size; j++) { //查找右边最大值
            max_right = max(max_right, height[j]);
        }
        ans += min(max_left, max_right) - height[i];
    }
        return ans;
    }
};

动态规划

暴力的思路由于会不断向左和向右搜索最大值，超时，可以先将数组的每个位置的最大值存储下来，这样就不用再搜索。

class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        int n=height.size();
        vector<int>left(n);
        vector<int>right(n);
        left[0]=height[0];
        for(int i=1;i<n;i++){
            left[i]=max(height[i],left[i-1]);//从左到右求最大值
        }
        right[n-1]=height[n-1];
        for(int i=n-2;i>=0;i--){
            right[i]=max(right[i+1],height[i]);//从右到左求最大值
        }
        for(int i=1;i<n;i++){
            ans+=min(left[i],right[i])-height[i];//最小最大值与高度差就是洼地
        }
        return ans;
    }
};

单调栈

class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0,i=0;
        int n=height.size();
        stack<int>sk;
        while(i<n){
            while(!sk.empty()&&height[sk.top()]<height[i]){
                int x=sk.top();
                sk.pop();
                if(sk.empty())break;
                int dis=i-sk.top()-1;//求矩形的长度
                int y=min(height[i],height[sk.top()])-height[x];//矩形的宽度
                ans+=dis*y;
            }
            sk.push(i++);
        }
        return ans;
    }
};