leetcode 42—— 接雨水

leetcode刷题计划第一天——42 接雨水

---

解题思路

首先分析题目。

针对 x = n 0 x=n_0 x=n0​ 的位置，求其往左遍历左侧柱子的最大值 m a x L e f t maxLeft maxLeft 和往右遍历右侧柱子最大值 m a x R i g h t maxRight maxRight ，取这两者当中较小的那个减去当前位置柱子高度 h e i g h t [ x ] height[x] height[x] ，即为此位置的蓄水量。

当然，如果当前位置 h e i g h t [ x ] > m i n ( m a x L e f t , m a x R i g h t ) height[x]>min(maxLeft,maxRight) height[x]>min(maxLeft,maxRight) ，此处需水量为0

根据这种思路，暴力解法即为，从每个位置 x x x 向左向右分别找到最大值，按照上述算法计算并累加即可。

但是很容易就能发现，上述算法在向左和向右比较最大值的过程中有大量的重复计算。

因此我们可以用空间换时间！定义两个数组， l e f t left left 和 r i g h t right right ，从左向右遍历，每一步的最大值记录在 l e f t left left 数组当中。

同理从右向左遍历，每一步的最大值记录在 r i g h t right right 数组当中。

最后查阅即可。

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        vector<int> left(n),right(n);
        int max_left=0,max_right=0;
        for(int i=0;i<n;++i){
            left[i]=max_left;
            right[n-1-i]=max_right;
            if(height[i]>max_left) max_left=height[i];
            if(height[n-1-i]>max_right) max_right=height[n-1-i];
        }
        int total_num=0;
        for(int i=0;i<n;++i){
            total_num+=max(min(left[i],right[i])-height[i],0);
        }
        return total_num;
    }
};