问题链接
42. 接雨水（困难）
问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例
解题思路
1.暴力解法：求每一列的雨水
遍历每一列（起始列和最后一列除外，因为不可能有雨水）：
往左右分别扩散，找到左、右边界的最高高度；
根据左、右最高高度以及当前柱形的高度，可以算出当前列存在的雨水。
2.动态规划
解1是一种暴力解法，但是找左右最高边界求每一列的思路是可以借鉴的；
解2是在这个思路的基础上，用动态规划来做优化：
A. 求最左边界：遍历数组，第i位的左最高边界就是max(第i-1位的左最高边界, 第i-1位的高度);
B. 求最右边界同理；
C. 再用一次遍历进行雨水求和。
3.单调栈
推荐阅读：【动画模拟】一下就能读懂（单调栈）
原理：当几个柱形形成了“U”型时，就计算一次面积
遍历数组，将数组中的数丢到单调递减栈里，当新进的数违反了单调性（新进的数大于栈顶元素），就计算一次面积：
A. 取出栈顶元素，作为矩形的下边界，记为low;
B. 继续查看栈顶元素：如果和原来的栈顶元素一样大，直接取出来；直到找到比原栈顶元素大的数，记为high;
C. 根据low、high以及遍历数组当前的位置，计算面积：(Math.min(height[i], height[high]) - height[low]) * (i - high - 1)。
4.基于解法1、解法2的思路，用双指针进行优化
这里不赘述，感觉看代码理解起来更快。。。
代码示例（JAVA）
1.暴力解法
class Solution {
public int trap(int[] height) {
int result = 0;
for (int i = 1; i < height.length - 1; i++) {
int left = 0, right = 0;
for (int j = i - 1; j >= 0; j--) {
left = Math.max(left, height[j]);
}
for (int j = i + 1; j <= height.length - 1; j++) {
right = Math.max(right, height[j]);
}
if (Math.min(left, right) > height[i]) {
result += Math.min(left, right) - height[i];
}
}
return result;
}
}
时间复杂度：O(n2)
执行结果
2.动态规划
class Solution {
public int trap(int[] height) {
int[] left = new int[height.length];
int[] right = new int[height.length];
// 左边界
for (int i = 0; i < height.length; i++) {
left[i] = i == 0 ? 0 : Math.max(left[i - 1], height[i - 1]);
}
// 右边界
for (int j = height.length - 1; j >= 0; j--) {
right[j] = j == height.length - 1 ? 0 : Math.max(right[j + 1], height[j + 1]);
}
// 求和
int result = 0;
for (int i = 0; i < height.length; i++) {
if (Math.min(left[i], right[i]) - height[i] > 0) {
result += Math.min(left[i], right[i]) - height[i];
}
}
return result;
}
}
时间复杂度：O(n)
执行结果
image.png
3.单调递减栈
class Solution {
public int trap(int[] height) {
Deque<Integer> deque = new LinkedList<>();
int result = 0;
for (int i = 0; i < height.length; i++) {
// 破坏单调递减，找雨水面积
while (!deque.isEmpty() && height[deque.peekLast()] < height[i]) {
int low = deque.pollLast();
// 移除和low相同高度的，找到第一个比low高的位置
while (!deque.isEmpty() && height[deque.peekLast()] == height[low]) {
deque.removeLast();
}
if (!deque.isEmpty()) {
int high = deque.peekLast();
// 计算面积
result += (Math.min(height[i], height[high]) - height[low]) * (i - high - 1);
}
}
// 入栈
deque.offerLast(i);
}
return result;
}
}
时间复杂度：O(n)
执行结果
4.双指针
class Solution {
public int trap(int[] height) {
int maxLeft = 0, maxRight = 0;
int left = 0, right = height.length - 1;
int result = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] > maxLeft) {
maxLeft = height[left];
} else {
result += maxLeft - height[left];
}
left++;
} else {
if (height[right] > maxRight) {
maxRight = height[right];
} else {
result += maxRight - height[right];
}
right--;
}
}
return result;
}
}
时间复杂度：O(n)
执行结果
