一、问题描述:
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
二、解题思路:
思路1:通过动态规划的预处理方式,分别计算每个柱子左右两侧的最大高度,然后通过遍历计算每个柱子的位置能够存储的水量,最终求得总的积水量。
- 代码示例:
public int trap(int[] height) {
int length = height.length;
if (length <= 2) return 0;
int[] maxLeft = new int[length];
int[] maxRight = new int[length];
// 记录每个柱子左边柱子最大高度
maxLeft[0] = height[0];
for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);
// 记录每个柱子右边柱子最大高度
maxRight[length - 1] = height[length - 1];
for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);
// 求和
int sum = 0;
for (int i = 0; i < length; i++) {
int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
if (count > 0) sum += count;
}
return sum;
}
- 时间复杂度为 O(n),空间复杂度为 O(n),
思路2:用单调栈计算能接的雨水总量。
找到高-低-高形状的凹槽。
通过维护一个单调栈,单调栈存储的是下标,满足从栈底到栈顶的下标对应的数组 height 中的元素递减。
遍历数组,只要当前遍历的元素 height[i] 大于栈顶元素 height[top],且栈中至少包含两个元素,就可以形成一个“凹槽”,height[i] 是右边界,top下面的元素是左边界 height[left] 。
凹槽的储水量 curheight = Math.min(height[left], height[i]) - height[top];
- 代码示例:
public int trap(int[] height) {
int result = 0; // 存储最终的接水量
Deque<Integer> stack = new LinkedList<Integer>(); // 单调栈,存储数组索引
int n = height.length; // 数组长度
for(int i = 0; i < n; ++i) {
// 当栈非空且当前柱子高度大于栈顶柱子高度时,可以接雨水
while(!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop(); // 弹出栈顶元素,表示当前可以接水的高度
if(stack.isEmpty())
break;
int left = stack.peek(); // 左边界,当前弹出元素的左边界
int curwidth = i - left - 1; // 当前可以接水的宽度
// 当前可以接水的高度,即左右边界的最小高度减去当前弹出元素的高度
int curheight = Math.min(height[left], height[i]) - height[top];
// 累加当前可以接水的体积
//System.out.println(i +" " + left + " " + top + " " + curwidth * curheight);
result += curwidth * curheight;
}
stack.push(i); // 将当前柱子索引压入栈中
}
return result; // 返回最终的接水量
}
- 时间复杂度为 O(n),空间复杂度也为 O(n)