42、接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 1:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
思路
1、遍历枚举：
- 分析示例可知一下特点：
- 当下完雨之后，整个图形是一个土字形。
- 因此，可以知道前半部分是按照递增处理的，后半部分是按照递减处理的。
- 所以，找到最大值位置（多个最大值没关系），分两种情况（前半段递增，后半段递减）统计即可。
2、动态规划
- 两个数组，记录左右最大高度数组
- 遍历数组，求出面积交际的区域，就是接到的雨水量
3、单调栈
用一个栈，存储遍历的结果，根据结果的大小，判断是继续入栈还是先出栈计算接水量。
- 当前元素大于栈顶元素，则计算其中区域的节水量，否则继续入栈
- 计算其中区域的接水量，需要逐个出栈进行计算。
4、双指针
动态规划的优化算法，我们可以：
- 只维护左右指针，以及左右当前的最大高度
- 没有相遇时：
- 更新左右最大值
1、左右坑洼枚举 $O(n^2)$
思路：只有坑洼出可以储水，那么按照以下思路进行计算水量：
- 从左到右，计算坑洼的水量，开始位置i,找到第一比i高的地方j，然后计算i-j内可以接到的雨水量。
class Solution {
public int trap(int[] height) {
int sum = 0;
int len = height.length;
boolean up = true;
int h2 = 0,h3;// 记录最大值的下标
for (int i = 0;i < height.length;i++) {// 上坡
h2 = i;// 记录开始位置
for (int j = i+1;j < height.length;j++) {// 顺序找到第一个不比我矮的
if (height[j] >= height[i]) {
h2 = j;
break;
}
}
if (h2 > i){// 找到了
int start = height[i];
for (int j = i+1;j < h2;j++){
sum += start - height[j];// 逐个位置更新水量
}
i = h2 - 1;
}else {// 没有一个比我高呀
break;// 退出循环，从左到右找到最大值
}
}
if (h2 < len - 1) {// 下坡
h3 = h2;
for (int i = len - 1;i >= h3;i--){// 下坡
h2 = i;// 记录开始位置
for (int j = i - 1;j >= h3;j--){// 逆序找第一个不比我矮的
if (height[j] >= height[i]) {
h2 = j; // 找到了
break;
}
}
if (h2 < i) {// 找到了
int start = height[i];
for (int j = i-1;j > h2;j--){
sum += start - height[j];// 逐个位置更新水量
}
i = h2 + 1;
}
}
}
return sum;
}
}
思路优化
- 我们可以先找到整个数组中的最大值及其下标，避免全量遍历的时间复杂度
- 左右开弓进行计算接到的雨水量
class Solution {
public int trap(int[] height) {
if(height==null || height.length<3)
return 0;
int area = 0;
int leftHeight = height[0];
int rightHeight = height[height.length-1];
int maxHeight = height[0];
int maxIndex = 0;
for(int i=1; i<height.length; i++){// 找到最大值，以及分割点
if(height[i] > maxHeight){
maxHeight = height[i];
maxIndex = i;
}
}
// 整体递增部分
for(int i=1; i<maxIndex; i++){
if(height[i] < leftHeight)
area += leftHeight-height[i];
else
leftHeight = height[i];
}
// 整体递减部分
for(int i=height.length-1; i>maxIndex; i--){
if(rightHeight > height[i])
area += rightHeight - height[i];
else
rightHeight = height[i];
}
return area;
}
}
2、动态规划 $O(n)$
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
// leftMax[i] 取当前遇到的最高的height
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
// rightMax[i] 取当前遇到的最高的height
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
3、单调栈 $O(n)$
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int n = height.length;
for (int i = 0; i < n; ++i) {
// height[i] 大于栈顶高度，则逐个出栈，计算可以接到的雨水量
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();// 循环逐个屁、pop
if (stack.isEmpty()) {
break;
}
// 栈中第一个元素的下标
int left = stack.peek();
int currWidth = i - left - 1;
// 这里 要去取一个最小高度，减去内部的高度值
int currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i);
}
return ans;
}
}
4、双指针 $O(n)$
本质是木桶效应
class Solution {
public int trap(int[] height) {
int ans = 0;
int n = height.length;
int left = 0;
int right = n - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
// case1 find save water in left
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;// move left
} else { // case2 find save water in right
ans += rightMax - height[right];
--right;// move right
}
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
