“给定数组,计算数组转化为高度图后能储存最大的雨水量。”
题目链接:
来源:力扣(LeetCode)
链接:42. 接雨水 - 力扣(LeetCode) (leetcode-cn.com)
给定 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
这个题就是求数组中两个最高的元素,最简单的方法就是从左向右和从右向左,分别判断并记录左右边的最大高度,然后计算每个下标位置能接的雨水量,该方法需要对每个下标位置使用O(n)的时间向两边遍历,所以总时间复杂度为O(n2)。
那么有没有办法进行优化呢?如果已经知道每个元素位置下两边的最大高度,那么就可以在O(n)的时间复杂度内解决问题,这时候就可以使用动态规划方法,在O(n)的时间内得到每个位置的最大高度。
因此可以在正向遍历数组时得到左边最大的每个元素值,反向遍历的时候得到数组右边最大的每个元素值,遍历每个下标位置即可得到能接的雨水总量,时间复杂度为O(n)。
在动态规划做法中,空间复杂度O(n),时间复杂度O(n),那么有没有办法将空间复杂度降到O(1)?注意到从左向右计算和从右向左计算,可以用双指针和两个变量来代替两个数组。
代码参考:
public class Solution//双指针
{
public int Trap(int[] height)
{
int left = -1; int right = 0;
int sum = 0;
for (int i = 0; i < height.Length; i++)
{
if (height[i] != 0 && left == -1)
{
left = i;
}
if (height[i]!=0)
{
right = i;
}
sum += height[i];
}
if (left == -1)
{
return 0;
}
int curHeight = Math.Min(height[left],height[right]);
int volume = 0;
while (left < right)
{
int tempL = left; int tempR = right;
while (left < right && height[left] <= curHeight)
{
left++;
}
while (left < right && height[right] <= curHeight)
{
right--;
}
volume += curHeight * (left - tempL - right + tempR);
curHeight++;
}
volume += height[left];
return volume - sum;
}
}
时间复杂度 : O(n)
其中n是数组的长度。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
这道题还可以使用单调栈来解题。
维护一个单调栈,单调栈存储的是下标,满足从栈底到栈顶的下标对应数组中的元素递减,然后从左到右遍历数组,遍历到i处时,如果栈内有两个元素,栈顶元素top,下一个元素left,这样就可以得到一个可以接雨水的区域。
该区域的宽度是i-left-1,高度是min(height[left],height[i])-height[top],就可以根据宽度和高度计算得到该区域能接的雨水量。