题目:接雨水
给定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 <= 2 * 10^4
0 <= height[i] <= 10^5思路1
把最大值位置找到，再乘数组长度，求出矩形面积(总面积)，然后把白色部分面积和黑色部分面积减掉，就是雨水的面积。
- 时间复杂度:O(n)
- 空间复杂度:O(1)
代码
public int trap(int[] height) { // 总时间复杂度：O(n)
// 数组长度
int length = height.length;
// 如果数组长度<=2的话,接雨水量为0
if (length <= 2) {
return 0;
}
// 最大值位置
int maxIndex = 0;
// 矩形面积(总面积)
int SumArea = 0;
// 黑色部分面积
int blackArea = 0;
// 最大值位置左边白色部分面积
int whiteAreaLeft = 0;
// 最大值位置右边白色部分面积
int whiteAreaRight = 0;
// 遍历一遍数组,求出矩形面积和黑色部分面积和最大值位置
for (int i = 0; i < length; i++) { // 时间复杂度：O(n)
blackArea += height[i];
if (height[i] > height[maxIndex]) {
maxIndex = i;
}
}
SumArea = height[maxIndex] * length;
// 从左边遍历数组,直到最大值位置为止,求出左边白色部分面积
int maxLeft = height[0];
for (int left = 0; left <= maxIndex; left++) { // 时间复杂度：O(n)
// 找到一根更高的柱子,更新白色部分面积和数组中左边最大值
if (height[left] > maxLeft) {
whiteAreaLeft += left * (height[left] - maxLeft);
maxLeft = height[left];
}
}
int maxRigtht = height[length - 1];
// 从右边遍历数组,直到最大值位置,求出右边边白色部分面积
for (int right = length - 1; right >= maxIndex; right--) { // 时间复杂度：O(n)
// 找到一根更高的柱子,更新白色部分面积和数组中右边最大值
if (height[right] > maxRigtht) {
whiteAreaRight += (length - right - 1) * (height[right] - maxRigtht);
maxRigtht = height[right];
}
}
return SumArea - blackArea - (whiteAreaLeft + whiteAreaRight);
}思路2
暴力法:
直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。
- 时间复杂度:O(n²)
- 空间复杂度:O(1)
代码
public int trap(int[] height) {
// 数组长度
int length = height.length;
// 如果数组长度<=2的话,接雨水量为0
if (length <= 2) {
return 0;
}
// 雨水的面积
int sumArea = 0;
for (int i = 0; i < length; i++) {
// 每个元素左边最大高度
int maxLeft = 0;
// 每个元素右边边最大高度
int maxRight = 0;
for (int left = 0; left < i; left++) {
maxLeft = Math.max(height[left], maxLeft);
}
for (int right = length - 1; right > i; right--) {
maxRight = Math.max(height[right], maxRight);
}
// 每个元素的接雨水面积为两边最大高度的较小值减去当前高度的值。
int minHeight = Math.min(maxLeft, maxRight);
if (minHeight > height[i]) {
sumArea += minHeight - height[i];
}
}
return sumArea;
}思路3
动态规划:
在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。但是我们可以提前存储这个值。因此，可以通过动态规划解决。
这个概念可以见下图解释：
- 时间复杂度:O(n)
- 空间复杂度:O(n)
代码
public int trap(int[] height) { // 总时间复杂度：O(n)
// 数组长度
int length = height.length;
// 如果数组长度<=2的话,接雨水量为0
if (length <= 2) {
return 0;
}
// 雨水的面积
int sumArea = 0;
// 每个元素左边最大高度
int[] maxLeft = new int[length];
// 每个元素右边最大高度
int[] maxRight = new int[length];
maxLeft[0] = height[0];
for (int i = 1; i < height.length; i++) { // 时间复杂度：O(n)
maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
}
maxRight[length - 1] = height[length - 1];
for (int i = length - 2; i >= 0; i--) { // 时间复杂度：O(n)
maxRight[i] = Math.max(height[i], maxRight[i + 1]);
}
for (int i = 0; i < height.length; i++) { // 时间复杂度：O(n)
int minHeight = Math.min(maxLeft[i], maxRight[i]);
sumArea += minHeight - height[i];
}
return sumArea;
}思路4
单调栈的应用:
- 我们可以不用像思路3那样存储最大高度，而是用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。
- 我们可以先看一下gif图：
看gif图我们可以发现，遍历到某些柱子的时候，会由于和之前的某个柱子形成凹形的坑，接住雨水。 - 积水只能在低洼处形成，当后面的柱子高度比前面的低时，是无法接雨水的。所以使用单调栈储存可能储水的柱子，当找到一根比前面高的柱子，就可以计算接到的雨水。
单调栈就是比普通的栈多一个性质，即维护一个栈内元素单调。比如当前某个单调递减的栈的元素从栈底到栈顶分别是：[10, 9, 8, 3, 2]，如果要入栈元素5，需要把栈顶元素pop出去，直到满足单调递减为止，即先变成[10, 9, 8]，再入栈5，就是[10, 9, 8, 5]。 - 我们在遍历数组时维护一个单调递减栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到
sumArea。
- 时间复杂度:O(n)
- 空间复杂度:O(n)
代码
public int trap(int[] height) { // 总时间复杂度：O(n)
// 数组长度
int length = height.length;
// 如果数组长度<=2的话,接雨水量为0
if (length <= 2) {
return 0;
}
// 雨水的面积
int sumArea = 0;
Deque<Integer> stack = new LinkedList<>();
for (int current = 0; current < height.length; current++) {
// 当栈不为空,且当前元素大于栈顶元素时,计算面积
while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
// pop掉stackTopOne(当前栈顶元素)
int stackTopOne = stack.pop();
// 如果栈不为空,计算面积
if (!stack.isEmpty()) {
// stackTopTwo(当前栈顶元素)此时指向的是此次接住的雨水的左边界的位置。右边界是当前柱体位置，即current。
int stackTopTwo = stack.peek();
// current - stackTopTwo - 1 是雨水的宽度。
int distance = current - stackTopTwo - 1;
// Math.min(height[current], height[stackTopTwo])是左右柱子高度的最小值。
// minHeight减去height[stackTopOne]就是雨水的高度。
int minHeight = Math.min(height[current], height[stackTopTwo]);
sumArea += distance * (minHeight - height[stackTopOne]);
}
}
// 当栈为空,或者当前元素小于栈顶元素时,当前元素入栈
stack.push(current);
}
return sumArea;
}思路5
双指针:
我们先明确几个变量的意思：
maxLeft：左边的最大值，它是从左往右遍历找到的maxRight：右边的最大值，它是从右往左遍历找到的left：从左往右处理的当前下标right：从右往左处理的当前下标
maxRight
maxLeft __
__ | |
| |__ __?????????????????????? | |
__| |__| __| |__
left right- 定理一：在某个位置
i处，它能存的水，取决于它左右两边的最大值中较小的一个。 - 定理二：当我们从左往右处理到
left下标时，左边的最大值maxLeft对它而言是可信的，但maxRight对它而言是不可信的。
（见上图，由于中间状况未知，对于left下标而言，maxRight未必就是它右边最大的值） - 定理三：当我们从右往左处理到
right下标时，右边的最大值maxRight对它而言是可信的，但maxLeft对它而言是不可信的。
对于位置left而言，它左边最大值一定是maxLeft，右边最大值大于等于maxRight，这时候，如果maxLeft<maxRight成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的maxRight，都不影响这个结果。 所以当maxLeft<maxRight时，我们就希望去处理left下标，反之，我们希望去处理right下标
- 时间复杂度:O(n)
- 空间复杂度:O(1)
代码
public int trap(int[] height) { // 总时间复杂度：O(n)
// 数组长度
int length = height.length;
// 如果数组长度<=2的话,接雨水量为0
if (length <= 2) {
return 0;
}
// 雨水的面积
int sumArea = 0;
// 左指针(从左往右处理的当前下标)
int left = 0;
// 右指针(从右往左处理的当前下标)
int right = length - 1;
// 左边的最大值，它是从左往右遍历找到的
int maxLeft = height[0];
// 右边的最大值，它是从右往左遍历找到的
int maxRight = height[length - 1];
while (left < right) { // 时间复杂度：O(n)
// 当左边最大值小于右边最大值时,左边的最大值`maxLeft`是可信的,指针从左往右走(确保雨水不会从左边露出)
if (height[left] <= height[right]) {
// 左指针指针指向的值大于左边的最大值
if (height[left] > maxLeft) {
// 更新左边最大值
maxLeft = height[left];
} else {
// 计算面积
sumArea += maxLeft - height[left];
}
// 左指针指针往右走
left++;
} else {
// 右指针指针指向的值大于右边的最大值
if (height[right] > maxRight) {
// 更新右边最大值
maxRight = height[right];
} else {
// 计算面积
sumArea += maxRight - height[right];
}
// 右指针指针往左走
right--;
}
}
return sumArea;
}
