给定 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 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5] 输出:9
提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
动态规划:
class Solution {
public int trap(int[] height) {
int len = height.length;
// 如果数组长度为0,返回0
if(len == 0){
return 0;
}
// 创建一个数组用于存储每个位置左侧的最大高度
int[] leftMax = new int[len];
for(int i = 1; i < len; i++){
// 更新当前点的左侧最大高度
leftMax[i] = Math.max(height[i-1], height[i]);
}
// 创建一个数组用于存储每个位置右侧的最大高度
int[] rightMax = new int[len];
for(int i = len-2; i >= 0; i--){
// 更新当前点的右侧最大高度
rightMax[i] = Math.max(height[i], height[i+1]);
}
int ans = 0;
// 计算每个位置能够存储的水量
for(int i = 0; i < len; i++){
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
// 返回能够存储的总水量
return ans;
}
}
单调栈解决
import java.util.Stack;
class Solution {
public int trap(int[] height) {
// 初始化总雨水量为0
int totalWater = 0;
// 创建一个栈用于存储数组索引
Stack<Integer> stack = new Stack<>();
// 遍历每个高度
for (int i = 0; i < height.length; i++) {
// 当栈非空且当前高度大于栈顶所指的高度时
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
// 取出栈顶的高度索引
int top = stack.pop();
// 如果栈为空,跳出循环
if (stack.isEmpty()) {
break;
}
// 计算当前柱子的宽度
int distance = i - stack.peek() - 1;
// 计算能形成的水位高度差
int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
// 计算当前能积的水量并加到总水量中
totalWater += distance * boundedHeight;
}
// 将当前索引入栈
stack.push(i);
}
// 返回总雨水量
return totalWater;
}
}
在计算接雨水的过程中,水的高度取决于柱子之间的最低高度。具体来说,水只能被较矮的柱子挡住。因此,关键在于找到最低的柱子,并根据它来计算可能存储的水量。
class Solution {
public int trap(int[] height) {
int len=height.length;
int left=0,right=len-1;
int leftMax=0,rightMax=0;
int ans=0;
while(left<=right){
leftMax=Math.max(leftMax,height[left]);
rightMax=Math.max(rightMax,height[right]);
if(height[left]<height[right]){
ans+=leftMax-height[left];
left++;
}else{
ans +=rightMax-height[right];
right--;
}
}
return ans;
}
}
水量计算基础:
height[left] < height[right]
的情况,由于 leftMax
是从左侧移动过程中遇到的最大高度,而 rightMax
是从右侧移动过程中遇到的最大高度,因此:
height[left]
左侧的最大高度 leftMax
是可靠的。rightMax
还可能会更新。因此,此时计算 left
位置的积水量是安全的。为什么选择较小的高度:
height[left] < height[right]
,意味着在当前位置 left
,其右侧有更高的柱子。这个较高的柱子可以帮助挡住雨水。因此可以确定 leftMax
是最小的限制条件,用它来计算当前位置可能存储的水量是安全的。height[left] >= height[right]
,那么右侧柱子在此时成为决定因素,左侧的 leftMax
没有影响,应该通过 rightMax
计算右侧的水量。假设 height[left] = 2
,height[right] = 5
:
当 left
侧低于 right
侧:可以确定在左侧 left
柱子能容纳的水量只取决于 leftMax
。因此,将 left
向右移动并计算 leftMax - height[left]
。
如果反过来:如果左侧高于或等于右侧,则右侧可能会积水,因此移动 right
向左并计算 rightMax - height[right]
。
这一判断的核心在于:
right
指针right
指针初始位置:它从数组的最右端开始。left
指针初始位置:它从数组的最左端开始。height[left] < height[right]
在算法的开始阶段,我们用 height[left] < height[right]
来判断接下来的行动。虽然 right
一开始位于数组的最右边,但这并不影响算法的正确性,原因如下:
rightMax
的初始化:
rightMax
会等于 height[right]
。因为 right
指针在最右端,所以 rightMax
一开始就是数组最右边的那个高度。right
指针向左移动,rightMax
会逐渐更新为更大的值,直到遍历完所有右边的柱子。初始状态的判断:
left
和 right
的柱子高度进行比较。height[left] < height[right]
,说明左边的柱子比右边矮。在这种情况下,右边更高的柱子可以“挡住”水,因此左边柱子上方可能会有积水,这时候左边的积水高度是可以确定的,所以移动 left
指针并计算水量。height[left] >= height[right]
,算法会移动 right
指针。此时,不会计算 left
指针位置的积水,而是继续查看右边的柱子是否可能形成积水。意义在于确定安全的水量:
height[left]
和 height[right]
,算法确保了在当前位置计算水量时,有足够的信息保证水量是准确的。rightMax
和 leftMax
在算法执行过程中不断更新,确保算法总是在安全的条件下进行计算。即使 right
指针最开始位于最右边,这个初始比较也有意义,因为它为整个算法奠定了基础。我们可以通过这个初始比较,确保在移动 left
或 right
指针时,计算的积水量是正确且安全的。
假设 height
数组为 [1, 0, 2, 1, 0, 1, 3]
,left
和 right
初始分别在位置 0
和 6
:
left
开始为 1
,right
开始为 3
。height[left] = 1
,height[right] = 3
,显然 1 < 3
,我们可以放心地移动 left
指针,因为左边的积水高度确定不会超过 leftMax
。总之,这一步比较对于算法的正确性和水量计算至关重要,即使 right
指针最初处于最右边,也依然有效且必要。
因篇幅问题不能全部显示,请点此查看更多更全内容