LeetCode代码分析——42. Trapping Rain
2018-05-17 本文已影响2人
JackpotDC
题目描述
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
给出n个非负整数，代表一个海拔高度图，每个条的宽度是1，计算这个图中能够盛放多少水、
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
上面的海拔图代表数组[0,1,0,2,1,0,1,3,2,1,2,1]，在这个样例中，收集了6个单元格的水（蓝色选区）。感谢Marcos贡献的图片。
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
思路分析
方法一：栈的解决思路
经过对题目的仔细理解，可以发现，这个海拔图具有栈的特性，两个条的中间盛水，这个模型有些类似括号匹配。
例如[0,1,0,2,1,0,1,3,2,1,2,1]，在1-0-2的位置会有水，是因为1-0-2形成了一个坑，两边高，中间低。
在2-1-0-1-3的位置，会产生一个组合起来的坑，1-0-1形成的小坑和2-1-0-1-3上面的坑
2-1-0-1-3的拆分
如图，可以看到，大坑可以拆分为1-0-1组成的小坑和上面的坑。先计算小坑，再计算上面的坑，想到可以利用栈的特性。
遍历海拔图数组：
- 如果数组是逐个递减的，就将坐标入栈（之所以入栈坐标而不是海拔是因为后面要用坐标计算距离）
- 如果发现当前的值比栈顶高了（例如1-0遇到1），就循环从栈中pop出来数据，并且进行计算：(左右柱子最低的那个 - 坑底) * 左右柱子的距离，直到栈空了或者栈顶的柱子比当前高了
计算过程如图。
计算的过程
这样计算在遍历数组的基础上还要对栈进行操作，时间复杂度为O(n^2)，并不算最优解。
利用栈的代码实现
class Solution {
public int trap(int[] height) {
int res = 0;
LinkedList<Integer> stack = new LinkedList<>();
for (int i = 0; i < height.length; i++) {
if (stack.isEmpty() || height[i] < height[stack.peek()]) {
// 下坡，就入栈
stack.push(i);
} else {
// 发现上坡，就形成了坑，计算坑的容量
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int pre = stack.pop();
if (!stack.isEmpty()) {
res +=
(min(height[stack.peek()], height[i]) - height[pre])
* (i - stack.peek() - 1);
}
}
stack.push(i);
}
}
return res;
}
private int min(int a, int b) {
return a < b ? a : b;
}
}
references
https://segmentfault.com/a/1190000004594606
方法二：动态规划
思路分析
根据动态规划的思路分析，单独的看，要想知道每个点的水的深度，需要知道该位置的盛水能力。
一个位置的盛水能力在于该位置左右的上限最低的那个。（木桶效应，左右边界找短板）
求某位置的盛水能力
如图，因此，
某位置的盛水能力 = min(该位置左侧的最高点, 该位置右侧的最高点)
某位置的水深 = 该位置的盛水能力 - 该位置的底的高度
代码实现
class Solution {
public int trap(int[] height) {{
if (height == null || height.length == 0) {
return 0;
}
int max = 0;
int res = 0;
int[] container = new int[height.length];
for (int i = 0; i < height.length; i++) {
container[i] = max;
max = Math.max(max, height[i]);
}
max = 0;
for (int i = height.length - 1; i >= 0; i--) {
container[i] = Math.min(max, container[i]);
max = Math.max(max, height[i]);
res += container[i] - height[i] > 0 ? container[i] - height[i] : 0;
}
return res;
}
}
