Leetcode 42. 接雨水

题干

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length

• 1 <= n <= 2 * 104

• 0 <= height[i] <= 105

初见

遍历每一行，对于某一高度 h，在大于等于 h 的最左边柱子与大于等于 h 的最右边柱子之间的小于 h 的柱子在高度 h 可以接到雨水。时间复杂度 O(n^2)， AC 321/324 ，遗憾 TLE ：

class Solution {
    public int trap(int[] height) {
        int maxHeight = 0;
        for (int i = 0; i < height.length; i++) {
            maxHeight = maxHeight < height[i] ? height[i] : maxHeight;
        }
        int sum = 0;
        for (int i = 0; i <= maxHeight; i++) {
            sum += waterOfCertainHeight(height, i);
        }
        return sum;
    }

    public int waterOfCertainHeight(int[] height, int certainHeight) {
        int firstIndex = 0, lastIndex = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] >= certainHeight) {
                firstIndex = i;
                break;
            }
        }
        for (int i = height.length - 1; i >= 0; i--) {
            if (height[i] >= certainHeight) {
                lastIndex = i;
                break;
            }
        }
        if (firstIndex == lastIndex) {
            return 0;
        }
        int sum = 0;
        for (int i = firstIndex + 1; i < lastIndex; i++) {
            if (height[i] < certainHeight) {
                sum++;
            }
        }
        return sum;
    }
}

优化

解法一

TLE 的解法中，对于每一根柱子，都分别寻找其左侧与右侧的最高柱子，时间复杂度为 O(n^2)。可以通过两次遍历，提前将左侧与右侧最高的柱子进行预处理，时间复杂度降为 O(n)：

class Solution {
    public int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];

        leftMax[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = leftMax[i - 1] > height[i] ? leftMax[i - 1] : height[i];
        }
        rightMax[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = rightMax[i + 1] > height[i] ? rightMax[i + 1] : height[i];
        }

        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            sum += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return sum;
    }
}

解法二

单调栈。维护一个 height[i] 单调递减的栈（栈中存储下标 i ），当栈内至少有两个元素时，若 height[i] > height[stack.peek()] ，则退栈，将 bottom = height[stack.pop()] 作为底边高度， Math.Min(height[stack.peek()], height[i] 作为顶边高度（此处 peek() 为退栈后的），宽度为 i - stack.peek() - 1 ，即可求得这一部分所装水量。注意最后仍需将 height[i] 入栈；且对于同一个 i ，可能有多次退栈操作。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int bottomHeight = height[stack.pop()];
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currentWidth = i - left - 1;
                int currentHeight = Math.min(height[left], height[i]) - bottomHeight;
                sum += currentWidth * currentHeight;
            }
            stack.push(i);
        }
        return sum;
    }
}

解法三

双指针。维护两个指针left 和 right，以及两个变量 leftMax 和 rightMax，当两个指针没有相遇时，进行如下操作：

• 更新 leftMax 和 rightMax 的值；

• 如果 height[left] < height[right]，则必有 leftMax < rightMax，下标 left 处能接的雨水量等于 leftMax − height[left]， left++；

• 如果 height[left] >= height[right]，则必有 leftMax >= rightMax，下标 right 处能接的雨水量等于 rightMax − height[right]， right-- 。

class Solution {
    public int trap(int[] height) {
        int sum = 0, left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = leftMax > height[left] ? leftMax : height[left];
            rightMax = rightMax > height[right] ? rightMax : height[right];
            if (height[left] < height[right]) {
                sum += leftMax - height[left];
                left++;
            } else {
                sum += rightMax - height[right];
                right--;
            }
        }
        return sum;
    }
}