LeetCode42. 接雨水问题

本文主要是介绍LeetCode42. 接雨水问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode42. 接雨水问题

LeetCode地址

给定 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
0 <= n <= 3 * 104
0 <= height[i] <= 105

思路分析：

这道题我们可以使用三种不同的解法进行求解：

解法1：单调栈

我们定义一个单调栈，保证我们的栈内的元素是单调不减【即栈底到栈顶是单调不减的】，我们存储的是对应的元素的下标值

当遍历到的元素大于当前的栈顶元素：

先将栈顶元素pop出来
在判断此时栈是否为空，如果不为空，则我们定义栈顶元素作为我们的左边界left，则此时left到当前元素形成一个凹槽，可以进行雨水的存储，我们计算该区间能够存储的水的容量，并将该位置的值修改为凹槽的最小边界高度，即将其填平

无论如何，最后再将当前元素push到栈中

在这里插入图片描述

刚开始，我们的栈为空，我们遍历到第一个元素，将索引0存储到栈中

然后，第二个元素2小于栈顶元素，我们选择继续将其索引1存储到栈中，同理索引存储到栈中

当遍历到第4个元素的时候，此时当前的高度大于栈顶元素的高度0，故我们选择将栈顶元素pop出来

此时栈不为空，我们获取此时的栈顶元素的高度，即2，计算【2，0，3】区间能够接纳的雨水量，即为2，同时我们将索引2位置的值填充为2，如下图所示：

在这里插入图片描述

然后继续判断此时的栈顶元素（索引1）对应的高度2还是小于我们的当前高度3，则继续将栈顶元素pop出来，继续和上述一样的处理方式，将能够接纳的雨水量加入结果集中，同时更新对应位置的高度，如图所示：

在这里插入图片描述

故我们根据这种方式，一直维持单调栈，接下来的我们的柱子高度更新依次为：

在这里插入图片描述

最后更新求解我们的能够接到的雨水量

代码实现：

public int trap(int[] height) {int n = height.length;//定义一个单调栈：存储的数组的下标，使得下标对应的值单调递增Stack<Integer> stack = new Stack<>();int res = 0;for (int i = 0; i < n; i++) {int left = -1;while (!stack.isEmpty() && height[stack.peek()] < height[i]) {  //如果此时当前下标高度大于栈顶下标的高度//首先将栈顶元素pop出来stack.pop();//如果栈不为空，我们获取栈顶元素，进行凹区间的水量的计算if(!stack.isEmpty()){left = stack.peek();int min = Math.min(height[left],height[i]);for (int j = left + 1; j < i; j++) {res += min - height[j];height[j] = min;}}}stack.push(i); }return res;
}

解法2：动态规划

我们分别定义两个数组leftHeight和rightHeight，其中，**leftHeight[i]和rightHeight[i]**分别记录当前位置i的左边界和右边界的最大高度

则我们的当前位置的水量即为：
$d e p t h = M a t h . m i n (l e f t H e i g h t [i], r i g h t H e i g h t [i]) - h e i g h t [i];$

代码实现

class Solution {public int trap(int[] height) {int n = height.length;if(n <= 2) return 0;int[] leftHeight = new int[n];int[] rightHeight = new int[n];int res = 0; //结果集for(int i = 1; i < n - 1; i++) {  //第二个位置和最后一个位置没有左边界和右边界leftHeight[i] = Math.max(height[i - 1],leftHeight[i - 1]);}for(int i = n - 2; i > 0; i--) {rightHeight[i] = Math.max(height[i + 1],rightHeight[i + 1]);}//求解每一个位置的水量for(int i = 1; i < n - 1; i++) {int depth = Math.min(leftHeight[i],rightHeight[i]) - height[i];if(depth > 0) {res += depth;}}return res;}
}

解法3：双指针法

双指针的思想和上面的动态规划的思想是一致的：

代码实现

class Solution {public int trap(int[] height) {int n = height.length;if(n <= 2) return 0;int leftHeight = 0;int rightHeight = 0;int left = 0;int right = n - 1;int res = 0; //结果集while(left < right) {leftHeight = Math.max(leftHeight,height[left]);rightHeight = Math.max(rightHeight,height[right]);if(height[left] < height[right]) {res += leftHeight - height[left];++left;}else {res += rightHeight - height[right];--right;}}return res;}
}