亲宝软件园·资讯

展开

Leetcode_42. 接雨水

Keane1998 人气:3

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

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;
    }
};

加载全部内容

相关教程
猜你喜欢
用户评论