接雨水
题目描述:
给定 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
思路分析:
作为力扣的经典hard题和面经的常考题,本题的的解法也是非常多样。下面列举几种常见解法:
解法一:按行求
整个思路就是,求第 i 层的水,遍历每个位置,如果当前的高度小于 i,并且两边有高度大于等于 i 的,说明这个地方一定有水,水就可以加 111。
如果求高度为 i 的水,首先用一个变量 temp 保存当前累积的水,初始化为 000。从左到右遍历墙的高度,遇到高度大于等于 i 的时候,开始更新 temp。更新原则是遇到高度小于 i 的就把 temp 加 111,遇到高度大于等于 i 的,就把 temp 加到最终的答案 ans 里,并且 temp 置零,然后继续循环。
但这个解法现在 AC 不了了,会报超时,也就不展示代码了
解法二:按列求
求每一列的水,我们只需要关注当前列,以及左边最高的墙,右边最高的墙就够了。至于装水的多少,当然根据木桶效应,我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。
所以,根据较矮的那个墙和当前列的墙的高度可以分为两种情况。
- 较矮的墙的高度大于当前列的墙的高度
- 较矮的墙的高度小于等于当前列的墙的高度
只有当较矮的墙的高度大于当前列的墙的高度时才能存水,存水量为矮的墙的高度减去当前列的墙的高度。
代码展示:
class Solution {
public int trap(int[] height) {int sum = 0;//最两端的列不用考虑,因为一定不会有水。所以下标从 1 到 length - 2for (int i = 1; i < height.length - 1; i++) {int max_left = 0;//找出左边最高for (int j = i - 1; j >= 0; j--) {if (height[j] > max_left) {max_left = height[j];}}int max_right = 0;//找出右边最高for (int j = i + 1; j < height.length; j++) {if (height[j] > max_right) {max_right = height[j];}}//找出两端较小的int min = Math.min(max_left, max_right);//只有较小的一段大于当前列的高度才会有水,其他情况不会有水if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;
}
}
解法三: 动态规划
在解法二中,对于每一列,我们求它左边最高的墙和右边最高的墙,都是重新遍历一遍所有高度,这里我们可以优化一下。用两个数组记录当前每个列的左右最大值,避免重复遍历。
class Solution {public int trap(int[] height) {int sum = 0;//用来存放当前的左端最大值int[] max_left = new int[height.length];//用来存放当前的右端最大值int[] max_right = new int[height.length];//如果即将存入的的高度大于当前左端最大值,则替换最大值for (int i = 1; i < height.length - 1; i++) {max_left[i] = Math.max(max_left[i - 1], height[i - 1]);}//如果即将存入的的高度大于当前右端最大值,则替换最大值for (int i = height.length - 2; i >= 0; i--) {max_right[i] = Math.max(max_right[i + 1], height[i + 1]);}//找出两端较小的,只有较小的一段大于当前列的高度才会有水,其他情况不会有水for (int i = 1; i < height.length - 1; i++) {int min = Math.min(max_left[i], max_right[i]);if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;}
}
解法四:双指针
动态规划中,我们常常可以对空间复杂度进行进一步的优化。例如这道题中,可以看到,max_left [ i ] 和 max_right [ i ] 数组中的元素我们其实只用一次,然后就再也不会用到了。所以我们可以不用数组,只用两个指针就行了。
首先比较当前列左右两墙的高度大小,将那个较小的与当前列进行比较
class Solution {public int trap(int[] height) {int sum = 0,maxleft = 0,maxright = 0;//左指针加进去int left = 1;// 加右指针进去int right = height.length - 2; for (int i = 1; i < height.length - 1; i++) {//如果左指针的前一个值小于右指针的后一个值if (height[left - 1] < height[right + 1]) {//那么从左到右更,记录当前左端最大值maxleft = Math.max(maxleft, height[left - 1]);//如果当前左指针指向的高度小于左墙,则两者的高度差即为存水量if (maxleft > height[left]) {sum = sum + (maxleft - height[left]);}left++;} //否则从右到左更,记录当前右端最大值else {maxright = Math.max(maxright, height[right + 1]);//如果当前右指针指向的高度小于右墙,则两者的高度差即为存水量if (maxright > height[right]) {sum = sum + (maxright - height[right]);}right--;}}return sum;}
}