给定n个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
https://leetcode-cn.com/problems/trapping-rain-water/
示例1：
image输入：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
0 <= n <= 3 * 104
0 <= height[i] <= 105
Java解法
思路：
- 雨水的面积=左边界*（左边界与右边界的间距）-中间柱子面积
- 这里可以用双指针法，从左侧遍历找到不为0的柱子，右指针找到比左边界高的柱子，计算该值
- 左指针指向右指针，继续，直到右侧
- Emmm 想错一步，当左指针指向最高柱子时，后续处理会很麻烦（漏掉了4,2,3这种情况）
- 这里的改进是当移动到最高柱子时，从右侧倒着遍历一遍，遍历到最高位置，这里的逻辑是一样的。效率还不错，代码可以优化下，但思路可以了
package sj.shimmer.algorithm.ten_3;
/**
* Created by SJ on 2021/2/18.
*/
class D25 {
public static void main(String[] args) {
System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
System.out.println(trap(new int[]{4, 2, 3}));
}
public static int trap(int[] height) {
int result = 0;
if (height != null && height.length != 1) {
int left = 0;
int temp = 0;
boolean hasLeft = false;
int length = height.length;
for (int i = left; i < length; i++) {
if (!hasLeft) {
if (height[i] != 0) {
left = i;
hasLeft = true;
}
} else {
if (height[i] >= height[left]) {
result += temp;
temp = 0;
left = i;
} else {
temp += height[left] - height[i];
if (i == length - 1) {
temp = 0;
int right = length - 1;
//当前left是最长的柱子，进行逆向求取
for (int j = length - 1; j > left; j--) {
if (height[right] == 0) {
right = j;
continue;
}
if (height[j] >= height[right]) {
result += temp;
temp = 0;
right = j;
} else {
temp += height[right] - height[j];
if (j == left + 1) {
return result + temp;
}
}
}
}
}
}
}
}
return result;
}
}
image
官方解
https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
-
暴力
对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值
相当于说：每次遍历找到当前柱子所在的水坑的最大深度，把当前柱子体积累加，在继续查找下一个柱子
public int trap(int[] height) { int ans = 0; int size = height.length; for (int i = 1; i < size - 1; i++) { int max_left = 0, max_right = 0; for (int j = i; j >= 0; j--) { //Search the left part for max bar size max_left = Math.max(max_left, height[j]); } for (int j = i; j < size; j++) { //Search the right part for max bar size max_right = Math.max(max_right, height[j]); } ans += Math.min(max_left, max_right) - height[i]; } return ans; }- 时间复杂度： O(n^2)
- 空间复杂度： O(1)
-
动态编程
相比较上方，多了对每个柱子所在水坑的最大深度存储，减少了时间计算，算是以空间换时间了
public int trap(int[] height) { if (height == null || height.length == 0) return 0; int ans = 0; int size = height.length; int[] left_max = new int[size]; int[] right_max = new int[size]; left_max[0] = height[0]; for (int i = 1; i < size; i++) { left_max[i] = Math.max(height[i], left_max[i - 1]); } right_max[size - 1] = height[size - 1]; for (int i = size - 2; i >= 0; i--) { right_max[i] = Math.max(height[i], right_max[i + 1]); } for (int i = 1; i < size - 1; i++) { ans += Math.min(left_max[i], right_max[i]) - height[i]; } return ans; }- 时间复杂度： O(n)
- 空间复杂度： O(n)
-
栈的应用
用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。
主要思想就是 栈底存放左边界，新加元素做边界判断，满足时算出距离与高度值累加，然后弹出，继续判断
public int trap(int[] height) { int ans = 0, current = 0; Deque<Integer> stack = new LinkedList<Integer>(); while (current < height.length) { while (!stack.isEmpty() && height[current] > height[stack.peek()]) { int top = stack.pop(); if (stack.isEmpty()) break; int distance = current - stack.peek() - 1; int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top]; ans += distance * bounded_height; } stack.push(current++); } return ans; }- 时间复杂度： O(n)
- 空间复杂度： O(n)；最坏情况下
-
双指针
解法思想类似，角度不同、写法优雅
public int trap(int[] height) { int left = 0, right = height.length - 1; int ans = 0; int left_max = 0, right_max = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { ans += (left_max - height[left]); } ++left; } else { if (height[right] >= right_max) { right_max = height[right]; } else { ans += (right_max - height[right]); } --right; } } return ans; }- 时间复杂度： O(n)
- 空间复杂度： O(1）
