☆打卡算法☆LeetCode 42、接雨水 算法解析
☆打卡算法☆LeetCode 42、接雨水 算法解析
一、题目
1、算法题目
“给定数组，计算数组转化为高度图后能储存最大的雨水量。”
题目链接：
来源：力扣（LeetCode）
链接：42. 接雨水 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定 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二、解题
1、思路分析
这个题就是求数组中两个最高的元素，最简单的方法就是从左向右和从右向左，分别判断并记录左右边的最大高度，然后计算每个下标位置能接的雨水量，该方法需要对每个下标位置使用O(n)的时间向两边遍历，所以总时间复杂度为O(n2)。
那么有没有办法进行优化呢？如果已经知道每个元素位置下两边的最大高度，那么就可以在O(n)的时间复杂度内解决问题，这时候就可以使用动态规划方法，在O(n)的时间内得到每个位置的最大高度。
因此可以在正向遍历数组时得到左边最大的每个元素值，反向遍历的时候得到数组右边最大的每个元素值，遍历每个下标位置即可得到能接的雨水总量，时间复杂度为O(n)。
在动态规划做法中，空间复杂度O(n)，时间复杂度O(n)，那么有没有办法将空间复杂度降到O(1)？注意到从左向右计算和从右向左计算，可以用双指针和两个变量来代替两个数组。
2、代码实现
代码参考：
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;
}
}
3、时间复杂度
时间复杂度 ： O(n)
其中n是数组的长度。
空间复杂度： O(1)
只需要常数级别的空间存放变量。
三、总结
这道题还可以使用单调栈来解题。
维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应数组中的元素递减，然后从左到右遍历数组，遍历到i处时，如果栈内有两个元素，栈顶元素top，下一个元素left，这样就可以得到一个可以接雨水的区域。
该区域的宽度是i-left-1，高度是min(height[left],height[i])-height[top]，就可以根据宽度和高度计算得到该区域能接的雨水量。