Leetcode_42. 接雨水

经典的一个题，通过观察可以发现，每个高度能接的水就是左右两边分别的最大值的最小值再减去本身高度。

code

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        vector<int> mxl(n,-1),mxr(n,-1);
        int mx=0;
        for(int i=0;i<n;i++){
            mx=max(mx,height[i]);
            mxl[i]=mx;
        }
        mx=0;
        for(int i=n-1;i>=0;i--){
            mx=max(mx,height[i]);
            mxr[i]=mx;
        }
        int ans=0;
        for(int i=0;i<n;i++){
            ans+=min(mxl[i],mxr[i])-height[i];
        }
        return ans;
    }
};