42 接雨水
接雨水的本质:对于下标 i,下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值,下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]
暴力解法
通过循环找出下标 i 两边的最大高度leftMax和rightMax,再求最小值,这个最小值就是下标 i 处的水能到达的最大高度
leftMax和rightMax计算过程包含height[i]
下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int res = 0;
for(int i = 0; i < n; i++){
int leftMax = 0, rightMax = 0;
// 记得leftMax包含height[i]
for(int j = 0; j <= i; j++){
leftMax = max(leftMax, height[j]);
}
// 记得rightMax包含height[i]
for(int j = i; j < n; j++){
rightMax = max(rightMax,height[j]);
}
if(leftMax < rightMax){
res += leftMax - height[i];
}
else
res += rightMax - height[i];
}
return res;
}
};
时间复杂度:\(O(2n^2)\)
空间复杂度:\(O(n)\)
动态规划
在暴力解法的基础上分析,我们发现,每次从i左右两侧遍历寻找最高度需要\(O(n)\),这里面重复了很多次
我们干脆一次遍历使用数组记录leftMax[i]和rightMax[i]
- leftMax[i]表示i左侧高度最大值
- rightMax[i]表示i右侧高度最大值
观察代码你会发现,其实也就是将第二层for循环提到外面
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int res = 0;
// leftMax[i]表示i左侧高度最大值
// rightMax[i]表示i右侧高度最大值
int leftMax[n], rightMax[n];
// 初始化
leftMax[0] = height[0];
rightMax[n - 1] = height[n - 1];
// 更新leftMax和rightMax
for (int i = 1; i < n; i++) {
// 记得leftMax包含height[i]
leftMax[i] = max(leftMax[i - 1],height[i]);
}
for (int i = n - 2; i >= 0; i--) {
// 记得rightMax包含height[i]
rightMax[i] = max(rightMax[i + 1],height[i]);
}
for (int i = 0; i < n; i++) {
if (leftMax[i] < rightMax[i]) {
res += leftMax[i] - height[i];
} else
res += rightMax[i] - height[i];
}
return res;
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(n)\)
单调栈法
单调栈特点:
- 栈内记录下标
- 单调递减栈
- 栈底到栈顶,元素单调递减
- 当遇到height[i] > height[stk.top()],需要弹出栈顶元素,此时大小关系有:
- height[i] > height[stk.top()]
- 弹出栈顶元素
int idx = stk.top();- height[stk.top()] >= height[idx],这里的stk.top()与第一步的stk.top()不同
从左到右遍历数组,遍历到下标 i 时,如果栈内至少有两个元素,记栈顶元素为 top,top 的下面一个元素是 left,则一定有 height[left]≥height[top]。如果 height[i]>height[top],则得到一个可以接雨水的区域
- 该区域的宽度是 i−left−1
- 当height[i]>height[top],我们找到了两侧最大值,分别为rightMax(height[i])和leftMax(height[left]),两侧之间的区域就是接雨水的区域
- 由于接雨水区域不包括两侧最大值,因此width = i - left - 1
- 高度是 min(height[left],height[i])−height[top]
根据宽度和高度即可计算得到该区域能接的雨水量。
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
stack<int> stk;
int ans = 0;
for(int i = 0; i < n; i++){
// 这里注意用的是while 不是 if
while(!stk.empty() && height[i] > height[stk.top()]){
int idx = stk.top();
stk.pop();
// 记得判断边界条件
if(stk.empty())
break;
int left = stk.top();
int minHeight = min(height[left], height[i]);
ans += (minHeight - height[idx]) * (i - left - 1);
}
stk.push(i);
}
return ans;
}
};
双指针法
暴力解法本质上就是比较两侧元素大小,因此可以采用同侧双指针法优化
本题中,我们比较的是两侧高度最大值的最小值,因此分为两步
- 记录两侧高度的最大值 -> 在指针移动过程中进行
- 对两侧高度最大值进行取最小值 -> min(leftMax, rightMax)
问题在于如何求解下标 i 处能接的雨水量,即使用双指针后,下标i如何表示
- 双指针问题特性:left和right交替移动,最终遍历完整个数组,因此下标i实际上是移动的left和right
- 我们得到最小值后,立即计算这一侧的雨水量
- 如果leftMax < rightMax,那么计算res += leftMax - height[left];
- 如果leftMax > rightMax,那么计算res += rightMax - height[right];
- 这是因为,得到最小值后,我们会移动相应的指针。以leftMax < rightMax为例,假设当前left == 2,我们会更新left,之后我们不会再计算这个指针指向的height[2],因此计算雨水量使用leftMax - height[left]
- 为什么leftMax < rightMax,移动left
- 这是因为雨水量由最小值决定,如果移动rightMax,除非新的rightMax小于leftMax,否则对结果没有任何影响
- 而rightMax是递增的,每次都只会取更大值,即rightMax = max(rightMax, height[right]),因此rightMax不可能小于leftMax
- 因此我们移动最小值那一侧的指针
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int left = 0, right = n - 1;
int leftMax = height[left], rightMax = height[right];
int res = 0;
while(left < right){
leftMax = max(leftMax, height[left]);
rightMax = max(rightMax, height[right]);
if(leftMax < rightMax){
res += leftMax - height[left];
left++;
}
else{
res += rightMax - height[right];
right--;
}
}
return res;
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(1)\)
滑动窗口
滑动窗口算法可以用于解决一些字符串和数组问题,滑动窗口记录最大值、最小值、子串长度
例如:
- 字符串匹配问题,例如 Leetcode 第 28 题和第 76 题;
- 最长子串或子数组问题,例如 Leetcode 第 3 题、第 209 题和第 424 题;
- 最小覆盖子串问题,例如 Leetcode 第 76 题;
- 字符串排列问题,例如 Leetcode 第 567 题;
- 求解字符串或数组中的一些性质,例如 Leetcode 第 438 题、第 567 题和第 1004 题等。