网站建设和优司怎么样,2015网站备案教程,旅游网站设计图片,网站建设汇报方案ppt单调栈 概念#xff1a;维护栈中元素的单调性#xff0c;单调增或者单调减。 什么时候用#xff1f; 要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。单调栈的本质是空间换时间#xff0c;在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元…单调栈 概念维护栈中元素的单调性单调增或者单调减。 什么时候用 要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。单调栈的本质是空间换时间在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素优点是整个数组只需要遍历一次。因为我们遍历数组的时候我们不知道之前都遍历了哪些元素以至于遍历一个元素找不到是不是之前遍历过一个更小的所以我们需要用一个容器这里用单调栈来记录我们遍历过的元素。 如何用 当要求数组的每个元素的下一个最大元素时维护单调递减栈每次遇到栈顶元素新进栈元素时栈顶元素出栈如果出栈了新的栈顶还是小于新进栈元素则一直循环出栈进栈新元素进栈此时出栈的元素的右边第一个最大元素为新进栈元素。如果新进栈元素栈顶元素时则直接进栈。例如有数组 [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) {// 下一个更大单调递减队列HashMapInteger, Integer map new HashMap();StackInteger 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) {StackInteger stack new Stack();HashMapInteger, 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 {StackInteger stack ;HashMapInteger, 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 count1;}
}class StockSpanner {Dequeint[] stack;int idx;public StockSpanner() {stack new ArrayDequeint[]();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) {//从左往右维护递增栈记录出栈元素的下标取最小的下标//从右往左维护递减栈记录出栈元素的下标取最大的下标Stackint[] 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-left1;}}316. 去除重复字母 此题去重简单难点是字典序只要提到有序可以想到单调栈如果后面没有该字符则进栈或者出栈时不出栈(同时后一个字符不进栈)如果前面的字符比后面一个大且后面还有该字符则出栈如果前一个字符小则不出栈
import java.util.ArrayDeque;
public class Solution {public String removeDuplicateLetters(String s) {//使用单调栈保持字典序ArrayDequeCharacter stack new ArrayDequeCharacter();int length s.length();stack.addLast(s.charAt(0));StringBuffer res new StringBuffer();for(int i1;ilength;i){int flag 0;Character c stack.getLast();String sub s.substring(i,length);while (cs.charAt(i) !stack.contains(s.charAt(i)) sub.contains(c) !stack.isEmpty()){//栈顶元素大于待检测字符且栈中没有该元素且栈顶元素后续还有 且栈非空 则出栈stack.pollLast();if(!stack.isEmpty())c stack.getLast();flag 1;}if(flag1){// 出栈完成后待检测字符入栈stack.addLast(s.charAt(i));}if(!stack.contains(s.charAt(i))){ //cs.charAt(i) // 如果待检测字符小于c且栈中不包含它则直接进栈stack.addLast(s.charAt(i));}}while(!stack.isEmpty()){Character c stack.pollLast();res.append(c);}return res.reverse().toString();}
}
