- dp
维护两个dp数组，分别记录左侧和右侧的最大值。当前位置的雨水就是左右两侧最大值的较小值减去当前位置的高度，将所有雨水累加即可得到结果。
class Solution {
public int trap(int[] height) {
int n = height.length, left[] = new int[n], right[] = new int[n], res = 0;
for(int i = 0; i < n; i++){
left[i] = i == 0 ? height[0] : Math.max(left[i-1], height[i]);
right[n-1-i] = i == 0 ? height[n-1] : Math.max(right[n-i], height[n-1-i]);
}
for(int i = 0; i < n; i++)
res += Math.min(left[i], right[i])-height[i];
return res;
}
}
- 单调栈
- dp方法相当于竖直方向切分，单调栈方法相当于横向切分。
- 注意只有“高-矮-高”这种形式才可以接住雨水。
- 需要维护一个递减栈，从0开始进行遍历。如果栈不为空且栈顶元素小于当前元素，则pop出一个元素。pop出元素后，如果栈还不为空，那么满足了“高-矮-高”这种特性，横向切分后的高度等于两边较小值减去中间的较低值，即
Math.min(height[stk.peek()], height[i])-height[index]，宽度为两条高边的下标之差减一，即i-stk.peek()-1。如果pop出元素后栈为空，那么只能满足“矮-高”这种情况，无法存储雨水，则直接跳出循环。 - 循环结束后，将当前的下标存入栈中。
class Solution {
public int trap(int[] height) {
Deque<Integer> stk = new ArrayDeque<>();
int res = 0, n = height.length;
for(int i = 0; i < n; i++){
while(!stk.isEmpty() && height[stk.peek()] < height[i]){
int index = stk.pop();
if(stk.isEmpty()) break;
int w = i-stk.peek()-1, h = Math.min(height[stk.peek()], height[i])-height[index];
res += w*h;
}
stk.push(i);
}
return res;
}
}