Leetcode42. 接雨水

做法

考虑单独一列能生产多少贡献：用左右最大值去接这列的水

\(O(n)\)

Code

class Solution {

public:

        int mx[1000000],rx[1000000];

    int trap(vector<int>& height) {

        int n(height.size());

        // int mx(0);

        for(int i=0;i<n;++i){

            if(i==0) mx[i]=height[i];

            else mx[i]=max(mx[i-1],height[i]);

        }

        int ans(0);

        for(int i=n-1;i>=0;--i){

            if(i==n-1) rx[i]=height[i];

            else rx[i]=max(rx[i+1],height[i]);

            ans+=min(rx[i],mx[i])-height[i];

        }

        /*int ans(0);

        for(int i=0;i<n;++i){

            ans+=min(rx[i],mx[i])-height[i];

        }*/

        return ans;

    }

};

巴特西

Leetcode42. 接雨水

做法

Code

最新文章

热门文章