本文主要是介绍【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;}
这篇关于【Leetcode 42】 接雨水-单调栈解法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!