Leecode 42 接雨水

给定n A non-negative integer indicates the height map of each column with a width of 1, and calculates the columns arranged according to this, how much rainwater can be connected after rain.

The above is a height map represented by the array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, it can be connected to 6 units. Rain (blue part means rain). 谢谢 Marcos Contribute this image.

案例:

输入:[0,1,0,2,1,0,1,3,2,1,2,1]output:6 

Looked at the fastest speed code on leecode is really ugly no way...

is not as good as me, the speed is also the fastest, the idea is clear, the code is more elegant hhh

main That is to maintain two arrays indicating the maximum height of the left and right sides. If there is a left side higher than the current one and the right side is higher than the current one, then the as plus the difference between the left and right minimum heights is good.

static const auto __=[](){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> left;
        vector<int> right;
        for (int i = 0; i < height.size(); ++i)
        {
            left.push_back(height[i]);
            right.push_back(height[i]);
        }
        for (int i = 1; i < left.size(); ++i)
        {
            if (left[i-1] > left[i])
            {
                left[i] = left[i-1];
            }
        }
        for (int i = height.size() - 2; i >= 0; --i)
        {
            if (right[i+1] > right[i])
            {
                right[i] = right[i+1];
            }
        }
        int ans = 0;
        for (int i = 0; i < height.size(); ++i)
        {
            if (left[i] >= height[i] && right[i] >= height[i])
            {
                ans += min(left[i], right[i]) - height[i];
            }
        }
        return ans;
    }
};