【Leetcode 42】 接雨水-单调栈解法

 

基础思路：

维持栈单调递减，一旦出现元素大于栈顶元素，就可以计算雨水量，同时填坑（弹出栈顶元素）

需要注意：

单调栈通常保存的是下标，用于计算距离

public static int trap2(int[] height) {int result = 0;int n = height.length;LinkedList<Integer> stack = new LinkedList<>();for (int i = 0; i < n; i++) {if (stack.isEmpty() || height[i] < height[stack.getFirst()]) {//栈为空或者保持单调，压栈stack.addFirst(i);} else {//执行出栈操作直到栈单调，出栈过程相当于填水坑操作，同时记录当前雨量while (height[i] > height[stack.getFirst()]) {int elm = stack.pop();if (stack.isEmpty()) {break;}int wall = height[stack.getFirst()] < height[i] ? height[stack.getFirst()] : height[i];result += (wall - height[elm]) * (i - stack.getFirst() - 1);}//栈恢复单调后，压栈stack.addFirst(i);}}return result;}