LeetCode 42. 接雨水（单调栈&581双指针继）

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

1. 考虑每一列的接雨水总和
2. 维护leftMax(n),rightMax(n)（包括height[i]自身，否则可能会出现负数）

class Solution {
public:
    int trap(vector& height) {
        int ans=0;
        int n=height.size();
        vector leftMax(n),rightMax(n);
        leftMax[0]=height[0];
        for(int i=1;i
            leftMax[i]=max(leftMax[i-1],height[i]);
        }
        rightMax[n-1]=height[n-1];
        for(int i=n-2;i>=0;i--){
            rightMax[i]=max(rightMax[i+1],height[i]);
        }
        for(int i=1;i
        	//每一列能接到的雨水
            ans+=min(leftMax[i],rightMax[i])-height[i];
        }
        return ans;
    }
};

双指针，对解一优化

class Solution {
public:
    int trap(vector& height) {
        int ans=0;
        int l=0,r=height.size()-1;
        int leftMax=-1,rightMax=-1;
        while(l<=r){
        	//leftMax、rightMax维护左右最大值
        	//ans+=min(leftMax[i],rightMax[i])-height[i]
            leftMax=max(leftMax,height[l]);
            rightMax=max(rightMax,height[r]);
            if(leftMax
                ans+=leftMax-height[l];
                l++;
            }else{
                ans+=rightMax-height[r];
                r--;
            }
        }
        return ans;
    }
};

1. 将题目转换为，找到height[i]左右第一个比height[i]大的下标[left，right]
2. 考虑每一行的接雨水总和

class Solution {
public:
    int trap(vector& height) {
        int ans = 0;
        stack stk;
        int n = height.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }
};