题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
思考
建立一个栈,栈为空时,如果数大于0就push,并且保存第一个数,遍历,如果小于第一个数的就push,大于的话就开始pop,循环完成后可能会遇到栈底的数最大,栈不为空,就还需要进行一个循环,反过来计算直到栈为空
代码
import java.util.Stack;
class Solution {
public int trap(int[] height) {
Stack<Integer> stack = new Stack<>();
int count = 0;
int min = 0;
for (int x : height) {
if (stack.isEmpty() && x > 0) {
stack.push(x);
min = x;
} else if (!stack.isEmpty() && x < min) {
stack.push(x);
} else if (!stack.isEmpty() && x >= min) {
while (!stack.isEmpty()) {
if (min - stack.peek() > 0)
count += min - stack.pop();
else
stack.pop();
}
stack.push(x);
min = x;
}
}
int max = 0;
while (!stack.isEmpty()) {
if (max == 0) {
max = stack.pop();
} else if (max <= stack.peek()) {
max = stack.pop();
} else {
count += max - stack.pop();
}
}
return count;
}
}