42. 接雨水

Problem: 42. 接雨水。比较朴素的做法。

思路

我们用列的方式看这道题，先从左向右看，用双指针维护一个区间，这个区间满足区间右端点的高度大于等于左端点，这样这个区间内的水量可以用左端点高度乘以开区间宽度减去开区间内柱子高度求得。

但是这个求法可能无法解决最右边的区间水量。显然，从左往右看和从右往左看是一样的，我们只需要从右往左看到最后一个区间的开头，求出那一部分的水量，再加上去即可。

第二个做法为什么可行呢？因为当我们求不出最后一个区间的水量时，区间开头的高度一定是大于区间内的所有点的，这样从右往左算一定可以算出来。

复杂度

• 时间复杂度: $O(n)$。最坏情况遍历两次数组，n为数组长度。
• 空间复杂度: $O(1)$。

Code

class Solution {
    public int trap(int[] height) {
        int i = 0;
        int n = height.length;
        int ret = 0;
        while (i < n && height[i] == 0) i++;
        while (i < n) {
            int start = i;
            int curSum = 0;
            i++;
            while (i < n && height[i] < height[start]) {
                curSum += height[i];
                i++;
            }
            if (i == n) {
                i = start;
                break;
            }
            ret = ret + (i - start - 1) * Math.min(height[start], height[i]) - curSum;
        }
        int j = n - 1;
        while (j > i) {
            int start = j;
            int curSum = 0;
            j--;
            while (j > i && height[j] < height[start]) {
                curSum += height[j];
                j--;
            }
            ret = ret + (start - j - 1) * Math.min(height[start], height[j]) - curSum;
        }
        return ret;
    }
}