代码思路一(单调栈)
一层一层的去计算容量,单调递减栈可以线性的增加每一层,容量不会多加或者少加,通过遍历单调栈时候肯定是按照从小到大的顺序遍历,每一次的长度:可以通过当前i的高度和单调栈第二个的高度的最低减去单调栈栈顶的高度,宽度:通过当前的位置减去单调栈第二个的位置 - 1来确定,计算完这一层,继续寻找如果还是不小于栈顶,继续用上面的方法,直到找到小于栈顶或者栈为空,添加当前元素的坐标,遍历完数组中所有元素之后,就完成计算。
JavaLeetCode模式代码
class Solution {
public int trap(int[] height) {
Stack<Integer> stack = new Stack<Integer>();
int ans = 0;
for (int i = 0; i < height.length; i ++ ) {
while (stack.size() > 0 && height[i] > height[stack.peek()]) { // 栈不为空 并且 当前元素比栈顶高
int top = stack.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;
}
}