将大块问题分解成小块问题

题目链接-来源：力扣（LeetCode）

给定 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 个单位的雨水（蓝色部分表示雨水）。

思路：

如果把每一块相连的雨水作为一个整体来考虑，时间复杂度显然是不可接受的。我们尝试按每一列来考虑雨水容量。
对于任意一根柱子，其所在位置能否存放雨水，取决于其本身的高度以及「左侧最高柱子高度」以及「右侧最高柱子高度」当中的较小者（木桶原理）。于是我们需要为每一根柱子存储其「左侧最高柱子高度」以及「右侧最高柱子高度」，显然，这两个高度都能在 O(n) 时间求出，以「左侧最高柱子高度」（记为MaxLeft[i]）为例，MaxLeft[i] = max(MaxLeft[i - 1], height[i - 1])。
维护了 MaxLeft 和 MaxRight 数组以后，我们对每一根柱子 i，只需取两个 Max 值的较小者，记为 top，当 top > height[i]时，我们就在答案中累加进这个差值。最终遍历所有柱子后，即可得出结果。
注意对于编号为 0 和 n - 1 的柱子，有一侧的最高柱子高度始终为 0，我们可以直接省略。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int trap(int[] height) {
        
        // Init
        int n = height.length;
        int pMaxLeft = 0, pMaxRight = n - 1;
        for (int i = 1, j = n - 2; i < n; i++, j--) {
            MaxLeft[i] = Integer.max(MaxLeft[i - 1], height[i - 1]);
            MaxRight[j] = Integer.max(MaxRight[j + 1], height[j + 1]);
        }
        
        // Solute
        int ans = 0;
        
        for (int i = 1; i < n - 1; i++) {
            int top = Integer.min(MaxLeft[i], MaxRight[i]), cur = height[i];
            if (cur < top) {
                ans += top - cur;
            }
        }
        return ans;
    }
}