单调栈题目

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

下一个更大元素

下一个更大元素

思路：

这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「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;
    }
}