給定n個非負整數(shù)表示每個寬度為 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
解釋：上面是由數(shù)組 [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的柱子灸芳，右指針找到比左邊界高的柱子涝桅，計算該值
- 左指針指向右指針，繼續(xù)烙样，直到右側
- Emmm 想錯一步苹支，當左指針指向最高柱子時，后續(xù)處理會很麻煩（漏掉了4,2,3這種情況）
- 這里的改進是當移動到最高柱子時误阻，從右側倒著遍歷一遍债蜜，遍歷到最高位置，這里的邏輯是一樣的究反。效率還不錯寻定，代碼可以優(yōu)化下，但思路可以了
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;
//當前l(fā)eft是最長的柱子精耐，進行逆向求取
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/
-
暴力
對于數(shù)組中的每個元素狼速，我們找出下雨后水能達到的最高位置，等于兩邊最大高度的較小值減去當前高度的值
相當于說：每次遍歷找到當前柱子所在的水坑的最大深度卦停，把當前柱子體積累加向胡，在繼續(xù)查找下一個柱子
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)
-
動態(tài)編程
相比較上方，多了對每個柱子所在水坑的最大深度存儲惊完，減少了時間計算僵芹，算是以空間換時間了
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)
-
棧的應用
用棧來跟蹤可能儲水的最長的條形塊。使用棧就可以在一次遍歷內(nèi)完成計算小槐。
主要思想就是 棧底存放左邊界拇派，新加元素做邊界判斷，滿足時算出距離與高度值累加凿跳，然后彈出件豌，繼續(xù)判斷
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)；最壞情況下
-
雙指針
解法思想類似控嗜，角度不同茧彤、寫法優(yōu)雅
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）
