本文主要是介绍单调栈类型总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
核心思想就是: 3, 4，2， 从2往左看过去，第一个最大的数是4，所以3没必要存；
Trapping Rain Water 需要找到每个元素从左右两边看，左右两边第一个最大的元素，water 就是左右两边最大的最小值 - 当前的height；这样用单调递减栈，注意stack里面存的是index，用来求宽度的；
class Solution {public int trap(int[] height) {if(height == null || height.length == 0) {return 0;}int n = height.length;int res = 0;Stack<Integer> stack = new Stack<>();for(int i = 0; i < n; i++) {while(!stack.isEmpty() && height[stack.peek()] < height[i]) {int j = stack.pop();if(!stack.isEmpty()) {int left = stack.peek() + 1;int right = i - 1;int h = Math.min(height[stack.peek()], height[i]) - height[j];res += (right - left + 1) * h;}}stack.push(i);}return res;}
}Next Greater Element I 思路：这个题目很好，是单调栈的经典题型；找右边第一个比 num[i]要大的数，那么左边比num 小的数，就没必要存，左边只存比stack peek 大的数，那么就是单调递减栈。这题精妙的地方在于,用hashmap去存右边第一个比他大的数的mapping，也就是存右边第一个踢到这个数的num；如果没有人踢他，代表右边没有人比他大；getOrDefault(nums1[i], -1);
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {if(nums1 == null || nums2 == null) {return new int[0]; }Stack<Integer> stack = new Stack<Integer>();HashMap<Integer, Integer> hashmap = new HashMap<>();for(int i = 0; i < nums2.length; i++) {while(!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {int j = stack.pop();hashmap.put(nums2[j], nums2[i]);}stack.push(i);}int[] res = new int[nums1.length];for(int i = 0; i < nums1.length; i++) {res[i] = hashmap.getOrDefault(nums1[i], -1);}return res;}
}Daily Temperatures 跟上面题一样，也是找最左边和最右边的第一个最大值；也是单调递减栈；小的没必要存，踢掉比较小元素，记录 i - stack.pop()的距离；
class Solution {public int[] dailyTemperatures(int[] T) {if(T == null || T.length == 0) {return new int[0];}int[] res = new int[T.length];Stack<Integer> stack = new Stack<Integer>();for(int i = 0; i < T.length; i++) {while(!stack.isEmpty() && T[stack.peek()] < T[i]) {int j = stack.pop();res[j] = i - j;}stack.push(i);}return res;}
}Remove Duplicate Letters 单调递增栈保证了lexicographical order是最小的；为了保证字母顺序是最小的。那么也就是说，如果先遇见的字母，后面还有，而且比我当前的要靠后，那么pop之前的，先放我现在的。比如说bab, 先遇见b了，再遇见a，那么我看b后面还有，那么对不起，pop b，我后面再加上你。用stack来保存信息，并保存stack的信息永远是递增的，首先count一下字母的频率，遇见一个char，就把频率降低-1，如果当前遇见的char，已经被visit过了，那么直接跳过，如果没有，那么check count里面还有没有，没有就不pop，有的话，那么就pop，因为后面还有不要着急。然后最后再把stack里面的char组合起来，反向输送。
class Solution {public String removeDuplicateLetters(String s) {if(s == null || s.length() == 0) {return s;}char[] ss = s.toCharArray();boolean[] visited = new boolean[256];int[] scount = new int[256];for(int i = 0; i < s.length(); i++) {scount[ss[i]]++;}Stack<Character> stack = new Stack<Character>();// bab; remove first b;for(int i = 0; i < s.length(); i++) {scount[ss[i]]--;// abb, second b, skip;if(visited[ss[i]]) {continue;}while(!stack.isEmpty() && stack.peek() > ss[i] && scount[stack.peek()] > 0) {char c = stack.pop();visited[c] = false;}stack.push(ss[i]);visited[ss[i]] = true;}StringBuilder sb = new StringBuilder();while(!stack.isEmpty()) {sb.insert(0, stack.pop());}return sb.toString();}
}Online Stock Span 单调递减栈，也就是进来一个数，跟前面的数比较，如果peek <= value，pop，用node记录days和value，为什么要用days而不用count记录pop多少次，原因是，pop的次数，后面是不知道的，那么只能通过days来记录前面有多少个被pop出去了，所以只有记录days才行。记录历史的value和days即可；T: O(N); S: O(N)
class StockSpanner {private class Node {public int days;public int value;public Node(int days, int value) {this.days = days;this.value = value;}}private Stack<Node> stack;private int days;public StockSpanner() {this.stack = new Stack<Node>();this.days = 0;}public int next(int price) {int res = 0;Node node = new Node(++days, price);while(!stack.isEmpty() && stack.peek().value <= price) {stack.pop();}if(stack.isEmpty()) {res = node.days;} else {res = days - stack.peek().days;}stack.push(node);return res;}
}/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner obj = new StockSpanner();* int param_1 = obj.next(price);*/Shortest Subarray with Sum at Least K 这题跟Minimum Size Subarray Sum 很相似，不同的是，加入了负数，使得问题变复杂了。思路就是：求区间和，很容易想到prefixsum，这个很好求出，但是怎么扫描去求sum>=k的最小区间长度，sum[i] .... sum[j].... sum[k]
如果sum[i] > sum[j], sum[k] - sum[i] >=k, 那么sum[k] - sum[j] 更加>=k,同时j > i,那么j到k区间会更小，那么sum[i]就没必要存，发现这个性质那么就是单调栈，前面的数sum[i], 比当前的数sum[j]要大，就没必要存，那么栈里面就是单调递增的，我们要保持里面是递增的，那么后面进来的数，如果比last要小，则踢掉前面的数，为什么？是因为如果存了，last > i, future - last >= k, 那么future - i 更加>= k, 所以 last比i大，没必要存；
More detailed on this, we always add at the LAST position
B[d.back] <- B[i] <- ... <- B[future id]
B[future id] - B[d.back()] >= k && B[d.back()] >= B[i]
B[future id] - B[i] >= k too
前后都要进出，那么用deque可以满足要求。这里要注意一点，长度是 i - deque.peekFirst()。为什么，是因为sum[j] - sum[i] ，subarray的长度其实是i + 1,...j，那么就是j - i + 1 - 1 = j - i;
记住prefixsum，都要用long来防止溢出；
class Solution {public int shortestSubarray(int[] A, int K) {if(A == null || A.length == 0) {return -1;}int n = A.length;long[] prefixsum = new long[n + 1];prefixsum[0] = 0;for(int i = 1; i <= n; i++) {prefixsum[i] = prefixsum[i - 1] + A[i - 1];}Deque<Integer> arrayDeque = new ArrayDeque<Integer>();int res = Integer.MAX_VALUE;for(int i = 0; i <= n; i++) {while(!arrayDeque.isEmpty() && prefixsum[i] - prefixsum[arrayDeque.peekFirst()] >= K) {res = Math.min(res, i - arrayDeque.peekFirst());arrayDeque.pollFirst();}while(!arrayDeque.isEmpty() && prefixsum[i] <= prefixsum[arrayDeque.peekLast()]) {arrayDeque.pollLast();}arrayDeque.offer(i);}return res == Integer.MAX_VALUE ? -1 : res;}
}Next Greater Node In Linked List 思路：单调栈的算法, 这题如果是array非常直观，但是是linkedlist，无法知道index的信息，怎么办？那么我可以加入index的信息，递增的index，那么把linkedlist map成带index 的node array，每个node里面有index 信息，那么在求res[index] 的时候，就从node里面拿index，来populate结果了。扫两遍，O(N)。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {private class Node {public int index;public int value;public Node(int index, int value) {this.index = index;this.value = value;}}public int[] nextLargerNodes(ListNode head) {int length = getLength(head);int[] res = new int[length];ListNode cur = head;Stack<Node> stack = new Stack<Node>();int index = 0;while(cur != null) {Node node = new Node(index++, cur.val);while(!stack.isEmpty() && stack.peek().value < cur.val) {res[stack.pop().index] = cur.val;}cur = cur.next;stack.push(node);}return res;}private int getLength(ListNode head) {ListNode cur = head;int len = 0;while(cur != null) {len++;cur = cur.next;}return len;}
}Largest Rectangle in Histogram 求最大矩阵，就是求每个元素height * 最左边第一个小于他的元素 到右边第一个小于他的元素之间的距离；这样求左右第一个最小，我们用单调递增栈可以完成。注意stack里面存的是index；因为需要计算width，用index可以知道高度；反而用高度没法计算width； Trapping Rain Water 求两边最大是递减栈；这里需要求最小，用的是递增栈；
class Solution {public int largestRectangleArea(int[] heights) {if(heights == null || heights.length == 0) {return 0;}Stack<Integer> stack = new Stack<Integer>();int maxrectangle = 0;for(int i = 0; i <= heights.length; i++) {// -1是为了把栈里面所有的元素都弹出来计算的；1，2，3，4，5，-1int h = (i == heights.length) ? -1 : heights[i];while(!stack.isEmpty() && heights[stack.peek()] >= h) {int j = stack.pop();// 如果为空，那么就是0；int left = stack.isEmpty() ? 0 : stack.peek() + 1;int right = i - 1;int area = (right - left + 1) * heights[j];maxrectangle = Math.max(maxrectangle, area);}stack.push(i);}return maxrectangle;}
}Maximal Rectangle 学会了 Largest Rectangle in Histogram ，把矩阵的以每一列为底的histogram求出来，然后每个row带入到 largest rectangle in histogram的函数中去求最大的矩阵，那么就是这题的答案； 这题难点在于如何生成投影的矩阵，首先声明一个一模一样的size的矩阵，然后初始化第一行，然后根据上面一行生成下一行，然后用投影矩阵去计算；
class Solution {public int maximalRectangle(char[][] matrix) {if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {return 0;}int m = matrix.length;int n = matrix[0].length;int res = 0;int[][] A = new int[m][n];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(i == 0) {A[i][j] = matrix[i][j] == '1' ? 1 : 0;} else {if(matrix[i][j] == '0') {A[i][j] = 0;} else {A[i][j] = A[i - 1][j] + 1;}}}res = Math.max(res, largestRectangleArea(A[i]));}return res;}public int largestRectangleArea(int[] heights) {if(heights == null || heights.length == 0) {return 0;}Stack<Integer> stack = new Stack<>();int maxarea = 0;for(int i = 0; i <= heights.length; i++) {// -1是为了把栈里面所有的元素都弹出来计算的；1，2，3，4，5，-1int val = i == heights.length ? -1 : heights[i];while(!stack.isEmpty() && heights[stack.peek()] >= val) {int j = stack.pop();// 如果为空，那么就是0；int left = stack.isEmpty() ? 0 : stack.peek() + 1;int right = i - 1;maxarea = Math.max(maxarea, (right - left + 1) * heights[j]);}stack.push(i);}return maxarea;}
}Max Tree 思路：用单调递减栈，因为L, <x, <x....X, <x, <x, R, (L>X, R>X) X能够给他父亲的，只能是L , R中的一个. 所以，这题变成了找左右两边第一个比X大的点，取最小值，然后分别接到左右（看X是连接在L，R的左边还是右边）；
/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/public class Solution {/*** @param A: Given an integer array with no duplicates.* @return: The root of max tree.*/public TreeNode maxTree(int[] A) {if(A == null || A.length == 0) {return null;}Stack<TreeNode> stack = new Stack<TreeNode>();for(int i = 0; i <= A.length; i++) {TreeNode node = (i == A.length) ? new TreeNode(Integer.MAX_VALUE) : new TreeNode(A[i]);while(!stack.isEmpty() && stack.peek().val <= node.val){TreeNode curnode = stack.pop();//核心就是安排pop出来的点，是去L，还是R的左边还是右边；// 注意因为上面pop了，这里一定要判断一下stack是否为空；if(!stack.isEmpty() && node.val > stack.peek().val) {stack.peek().right = curnode;} else {// node.val <= stack.peek().val;node.left = curnode;}}stack.push(node);}return stack.pop().left;}
}这篇关于单调栈类型总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
