自己解法
这个题之前看过解法，又想到用栈，不过忘了为啥要用。从暴力解法来看，就是当前点左右两边最高值中的较小值（包括当前点），减去当前点的高度，就是当前点能接雨水的面积。
不过这种解法效率太低，优化的方法是计算当前点，左右两边比自己高的第一个位置，也就是卡住当前点的位置，然后计算被卡住的面积。利用栈保存一个从栈底到栈顶递减的队列，后续有大于等于栈顶的元素，说明栈顶被栈中元素和当前元素卡住，计算整体被卡住的面积。
class Solution {
public int trap(int[] height) {
if (height.length == 0) {
return 0;
}
Stack<Integer> s = new Stack<>();
s.add(0);
int ans = 0;
for (int i = 1; i < height.length; i++) {
while (height[i] >= height[s.peek()]) {
int m = s.pop();
if (s.isEmpty()) {
break;
}
// 计算被两边卡住部分的面积
int temp = (Math.min(height[i], height[s.peek()]) - height[m]) * (i - s.peek() - 1);
ans += temp;
}
s.push(i);
}
return ans;
}
}
官方解法
双指针解法，思路是找出当前点左右两边最大值中的较小值，左右两边分别维护一个最大值。
如果左边小于右边，就更新左边，意味着左边的最大值小于右边最大值，这个逻辑有点理解不了的地方，为啥当前左指针的值小于右指针，就说明左边的最大值小于右边的最大值。
这个是因为两边都是分别扫描过来的，只有左边小于右边，有两种可能，一种是左指针左边还有更大的值，这种更大的值，会移动指针，只有一种情况，就是小于了右边某个值，才会移动，还有就是这种左指针本身是最大值，那也是小于右边的值，刚比较过。
还有就是，只有当前边不是最高的，才会update这边，如果这边比较高，一个值就可以挺到最后。
class Solution {
public int trap(int[] height) {
if (height.length == 0) {
return 0;
}
int ans = 0;
int left = 0;
int right = height.length - 1;
int leftMax = height[left];
int rightMax = height[right];
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
ans += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
ans += rightMax - height[right];
}
right--;
}
}
return ans;
}
}
网友评论