算法单调栈—Java版

单调栈

• 概念：维护栈中元素的单调性，单调增或者单调减。

• 什么时候用？

  • 要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。单调栈的本质是空间换时间，在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。

• 如何用？

  • 当要求数组的每个元素的下一个最大元素时，维护单调递减栈，每次遇到栈顶元素<新进栈元素时，栈顶元素出栈，如果出栈了新的栈顶还是小于新进栈元素，则一直循环出栈进栈，新元素进栈，此时出栈的元素的右边第一个最大元素为新进栈元素。如果新进栈元素<栈顶元素时，则直接进栈。例如有数组 [3,5,1,4,8,3]的对应元素的下一个最大元素为[5,8,4,8,-1,-1]，-1表示没有。维护单调递减栈 s=[] ，首先3进栈，s=[3]，然后新进栈元素为5，比栈顶元素大，5进栈，3出栈，此时s=[5],即3右边第一个比它大的元素为5，然后是1比栈顶5小直接进栈，s=[5,1]；然后遇见4，此时1出栈，4进栈，即第一个比1大的元素是4 ，s=[5,4]。

  • 总结：找第一个/下一个最大元素，维护递减栈；找第一个/下一个最小元素，维护递增栈。

LeetCode练习

• 496. 下一个更大元素 I

  public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 下一个更大，单调递减队列HashMap<Integer, Integer> map = new HashMap<>();Stack<Integer> stack = new Stack<>(); for (int i = 0; i < nums2.length; i++) {if(stack.isEmpty()||stack.peek()>=nums2[i]){stack.push(nums2[i]);}while (!stack.isEmpty() && stack.peek()<nums2[i]){map.put(stack.peek(),nums2[i]);stack.pop();}stack.push(nums2[i]);}int[] res = new int[nums1.length];for (int i = 0; i < nums1.length; i++) {if(map.containsKey(nums1[i])){res[i] = map.get(nums1[i]);}else {res[i] = -1;}}return res;}
  

• 503. 下一个更大元素 II

  public int[] nextGreaterElements(int[] nums) {Stack<Integer> stack = new Stack<>();HashMap<Integer, Integer> map = new HashMap<>();int[] nums2 = new int[nums.length*2];for (int i = 0; i < nums2.length; i++) {nums2[i] = nums[i%nums.length];}for (int i = 0; i < nums2.length; i++) {if(stack.isEmpty() || nums2[stack.peek()]>=nums2[i]){stack.push(i);continue;}while (!stack.isEmpty() && nums2[stack.peek()]<nums2[i]){if(!map.containsKey(stack.peek())){map.put(stack.peek(),nums2[i]);}stack.pop();}stack.push(i);}int[] res = new int[nums.length];for (int i = 0; i < nums.length; i++) {if(map.containsKey(i)){res[i] = map.get(i);}else {res[i] = -1;}}return res;}
  

  • 901. 股票价格跨度

    以上都是寻找某个数字右边第一个更大/或者更小的元素；如果换成寻找左边第一个更大/更小的元素呢？寻找左边第第一个更大/更小的，如果给定了数组，那么只需要倒序遍历数字入栈出栈即可。如果数组未给定，例如本题，找左边连续更小的数量，那么可以每次入栈记录其下标和值，下标用来做减法求出连续更小的数量，值用来出栈入栈的比较。例如第二个解法，正确做法是维护一个单调减的栈。连续更小的数量是入栈元素下标减去最后一个出栈元素的下标。当然也可以使用第一个解法，记录每次入栈元素挤出去的个数，下一次该元素出栈时也应该算上这些挤出去的数量。

    import java.util.HashMap;
    import java.util.Stack;
    public class StockSpanner  {Stack<Integer> stack ;HashMap<Integer, Integer> map;public StockSpanner (){stack = new Stack<>();map = new HashMap<>();}public int next(int price) {//维护单调递减栈if(stack.isEmpty() || stack.peek()>price){stack.push(price);return 1;}int count = 0;while (!stack.isEmpty() && stack.peek()<=price){if(map.containsKey(stack.peek())){count += map.get(stack.peek());map.remove(stack.peek());}stack.pop();count += 1;}stack.push(price);map.put(price,count);return count+1;} 
    }
    

  • class StockSpanner {Deque<int[]> stack;int idx;public StockSpanner() {stack = new ArrayDeque<int[]>();stack.push(new int[]{-1, Integer.MAX_VALUE});idx = -1;}public int next(int price) {idx++;while (price >= stack.peek()[1]) {stack.pop();}int ret = idx - stack.peek()[0];stack.push(new int[]{idx, price});return ret;}
    }
    

• 581. 最短无序连续子数组

  • public int findUnsortedSubarray(int[] nums) {//从左往右维护递增栈，记录出栈元素的下标，取最小的下标//从右往左维护递减栈，记录出栈元素的下标，取最大的下标Stack<int[]> sta = new Stack<>();int left = nums.length-1;int right = 0;for (int i = 0; i < nums.length; i++) {if(sta.isEmpty() || sta.peek()[1]<=nums[i]){sta.push(new int[]{i,nums[i]});continue;}while (!sta.isEmpty() && sta.peek()[1]>nums[i]){left = Math.min(left,sta.peek()[0]);sta.pop();}}sta.clear();for (int i = nums.length-1; i >=0; i--) {if(sta.isEmpty() || sta.peek()[1]>=nums[i]){sta.push(new int[]{i,nums[i]});continue;}while (!sta.isEmpty() && sta.peek()[1]<nums[i]){right = Math.max(right,sta.peek()[0]);sta.pop();}}if(left == nums.length-1 && right == 0){return 0;}else{return right-left+1;}}
    

• 316. 去除重复字母

  此题去重简单，难点是字典序，只要提到有序可以想到单调栈；如果后面没有该字符则进栈，或者出栈时不出栈(同时后一个字符不进栈)；如果前面的字符比后面一个大，且后面还有该字符则出栈；如果前一个字符小则不出栈；

import java.util.ArrayDeque;
public class Solution {public String removeDuplicateLetters(String s) {//使用单调栈保持字典序ArrayDeque<Character> stack = new ArrayDeque<Character>();int length = s.length();stack.addLast(s.charAt(0));StringBuffer res = new StringBuffer();for(int i=1;i<length;i++){int flag = 0;Character c = stack.getLast();String sub = s.substring(i,length);while (c>s.charAt(i) && !stack.contains(s.charAt(i)) && sub.contains(""+c) && !stack.isEmpty()){//栈顶元素大于待检测字符且栈中没有该元素，且栈顶元素后续还有 且栈非空 则出栈stack.pollLast();if(!stack.isEmpty())c = stack.getLast();flag = 1;}if(flag==1){// 出栈完成后，待检测字符入栈stack.addLast(s.charAt(i));}if(!stack.contains(s.charAt(i))){  //c<s.charAt(i) &&// 如果待检测字符小于c且栈中不包含它则直接进栈stack.addLast(s.charAt(i));}}while(!stack.isEmpty()){Character c = stack.pollLast();res.append(c);}return res.reverse().toString();}
}