网站优化排名哪家性价比高_中国建设网app下载_推广关键词排名方法_代刷网站推广快速

单调栈用途不太广泛，只处理一类典型的问题，比如「下一个更大元素」，「上一个更小元素」等

下一个更大元素

下一个更大元素

思路：

这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的下一个更大元素呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的下一个更大元素，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2){HashMap<Integer,Integer> map=new HashMap();Stack<Integer> stack=new Stack();//nums2从右向左进栈for(int i=nums2.length-1;i>=0;i--){int ele=nums2[i];while(!stack.isEmpty()&&ele>=stack.peek()){//矮个子起开stack.pop();}if(stack.isEmpty()){map.put(ele,-1);}else{map.put(ele,stack.peek());}stack.push(ele);}int size=nums1.length;int[] res=new int[size];for(int i=0;i<size;i++){res[i]=map.get(nums1[i]);}return res;}
}

每日温度

每日温度

class Solution {public int[] dailyTemperatures(int[] temperatures) {Stack<Node> stack=new Stack();int size=temperatures.length;int[]res=new int[size];for(int i=size-1;i>=0;i--){int ele=temperatures[i];while(!stack.isEmpty()&&ele>=stack.peek().temper){//太矮了起开stack.pop();}if(stack.isEmpty()){res[i]=0;}else{res[i]=stack.peek().index-i;}stack.push(new Node(ele,i));}return res;}
}
class Node{int temper;int index;Node(int temper,int index){this.temper=temper;this.index=index;}
}

下一个更大元素2

下一个更大元素2

class Solution {public int[] nextGreaterElements(int[] nums) {//循环数组，直接将数组翻两倍int size=nums.length;int[]res=new int[size];Stack<Integer> stack=new Stack();for(int i=2*size-1;i>=0;i--){int ele=nums[i%size];while(!stack.isEmpty()&&ele>=stack.peek()){//太矮了起开stack.pop();}if(i<size){if(stack.isEmpty()){res[i]=-1;}else{res[i]=stack.peek();}}stack.push(ele);}return res;}
}

链表中的下一个更大节点

链表中的下一个更大节点

先把链表换成数组，因为进栈的顺序是从后往前。

/*** 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 {public int[] nextLargerNodes(ListNode head) {ListNode cur=head;ArrayList<Integer> arr=new ArrayList();while(cur!=null){arr.add(cur.val);cur=cur.next;}int size=arr.size();int[]res=new int[size];Stack<Integer> stack=new Stack();for(int i=size-1;i>=0;i--){int ele=arr.get(i);while(!stack.isEmpty()&&ele>=stack.peek()){//太矮了起开stack.pop();}if(stack.isEmpty()){res[i]=0;}else{res[i]=stack.peek();}stack.push(ele);}return res;}
}

队列中可以看到的人数

题目

class Solution {//思路：从右往左进栈，个子高的在栈底，遇到个子矮的挤出去，并记录个数，进栈之前算好结果public int[] canSeePersonsCount(int[] heights) {int size=heights.length;int[]res=new int[size];Stack<Integer> stack=new Stack();int count=0;for(int i=size-1;i>=0;i--){int ele=heights[i];count=0;while(!stack.isEmpty()&&ele>=stack.peek()){//太矮了stack.pop();count++;//把ele右边矮子挤出去count个}if(stack.isEmpty()){res[i]=count;}else{res[i]=count+1;}stack.push(ele);}return res;}
}