LeetCode 0042 - Trapping Rain Water
# Hints
栈
DP
双指针扫描
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given non-negative integers representing an elevation map where the width of each bar is , compute how much water it is able to trap after raining.
The above elevation map is represented by array . In this case, units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
# 题意
给定一个长为 的非负整数数组 ,从左往右有 根柱子,第 根柱子的高度为 ,宽度为 ,求这些柱子最多能盛多少体积的水。
# 题解
我们考虑从左往右扫描,不难想到,如果遇到柱子 满足 ,则区间 的盛水量已经可以计算,其中 为上次计算的末端。但是这样的方法无法处理柱子的最高峰的右侧。
方法1:栈。
既然无法一次性计算区间 的盛水量,那么我们就利用栈的性质将其分段计算。
我们用栈来维护柱子的标号 ,设 表示栈顶的柱子的标号。我们从左往右依次遍历每根柱子,如果发现 ,就说明我们可以将栈顶取出,并进行一些计算。
具体地讲,我们将栈顶取出并记为 ,同时获取下一个栈顶 ,那么区间 中高度为 的部分将被计算。如果出栈后栈为空,说明不存在盛水,我们不进行上述计算。
这可能有些难以理解,因此我们下面将对上图中的例子进行详细解释。
示例中 。
当 时,都是直接将 入栈,此时栈中元素为 。
当 时,发现 ,我们将栈顶取出,则有 。显然我们希望计算的是 处的、在 两根柱子之间的盛水体积,计算可得 。
此时栈中元素为 ,发现 ,我们将栈顶取出,计算可得 。
将 入栈,此时栈中元素为 。
当 时,发现 ,我们将栈顶取出,则有 。我们希望计算的是区间 即 中的盛水体积,其中高度低的部分我们已经计算过了,所以最终计算可得 。
将 入栈。此时栈中元素为 。
到此本示例已经求解完成,如果右侧还有其他柱子则可继续。
事实上,将判断条件 设为 亦可,不影响答案的正确性,但是上述的过程会有些许不同,例如标号 将会在 时才出栈。
因为每个下标至多入栈一次出栈一次,所以总的时间复杂度为 。
方法2:动态规划。
这个方法的思路巧妙而又简单。既然我们难以处理最高峰的右侧,不妨正反求解两次。
设 表示 左侧的柱子高度的最大值, 表示 右侧的柱子高度的最大值。显然柱子 处的盛水高度取决于其左右两侧最高的柱子,也就是取决于 和 ,那么柱子 处的盛水体积为 。
下图为官方题解中给出的示意图。
显然数组 和 都可以由简单线性递推求得,最后再线性遍历一次对答案求和即可,总的时间复杂度为 。
方法3:双指针扫描。
考虑在动态规划法中计算过的 和 ,当 时,柱子 处的盛水体积就取决于 ,反之则取决于 。
那么我们就可以维护两个指针 和 ,令 并从左往右移动, 并从右往左移动。当 时,我们可以放心地去计算左侧的答案而不会产生任何的错漏,反之亦然。这个保证是该方法正确的前提。
总的时间复杂度为 。
# AC代码(栈)
class Solution {
public:
int trap(vector<int> & height) {
// 初始化
int res = 0;
// 主循环
stack<int> s;
for (int i = 0; i < height.size(); i ++) {
// 处理
while (!s.empty() && height[i] >= height[s.top()]) {
// 出栈
int index = s.top();
s.pop();
// 更新答案
if (!s.empty()) {
int dist = i - s.top() - 1;
res += dist * (min(height[i], height[s.top()]) - height[index]);
}
}
// 入栈
s.push(i);
}
// 返回
return res;
}
};
# AC代码(动态规划)
class Solution {
public:
int trap(vector<int> & height) {
// 特判
if (height.empty()) {
return 0;
}
// 初始化
int n = height.size();
int dp_left[n + 5], dp_right[n + 5];
memset(dp_left, 0, sizeof(dp_left));
memset(dp_right, 0, sizeof(dp_right));
dp_left[n - 1] = height[n - 1];
dp_right[0] = height[0];
// 递推
for (int i = n - 2; i >= 0; i --) {
dp_left[i] = max(dp_left[i + 1], height[i]);
}
for (int i = 1; i <= n - 1; i ++) {
dp_right[i] = max(dp_right[i - 1], height[i]);
}
// 求解
int res = 0;
for (int i = 0; i <= n - 1; i ++) {
res += (min(dp_left[i], dp_right[i]) - height[i]);
}
// 返回
return res;
}
};
# AC代码(双指针扫描)
class Solution {
public:
int trap(vector<int> & height) {
// 特判
if (height.empty()) {
return 0;
}
// 初始化
int n = height.size();
int res = 0;
// 主循环
int left = 0, right = n - 1;
int max_left = 0, max_right = 0;
while (left < right) {
if (height[left] < height[right]) {
max_left = max(max_left, height[left]);
res += (max_left - height[left]);
left ++;
} else {
max_right = max(max_right, height[right]);
res += (max_right - height[right]);
right --;
}
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01