【栈】Leetcode 496 下一个更大元素I-Toy模板网

这篇具有很好参考价值的文章主要介绍了【栈】Leetcode 496 下一个更大元素I。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

---------------🎈🎈题目链接🎈🎈-------------------

【栈】Leetcode 496 下一个更大元素I,Leetcode,开发语言,leetcode,数据结构,java,算法

解法1 两个单调栈

两个栈进行操作，一个栈用来遍历寻找，一个栈用来保留
将待寻找的nums2中的元素入栈，之后遍历nums1，
如果栈顶元素大于nums1[i]，则记录max，记录后弹出栈顶元素至tempstack，继续遍历栈，直到找到相等的为止
如果栈顶元素小于nums1[i]，则弹出栈顶元素至tempstack
如果栈顶元素等于nums1[i]，则停止对栈mystack的操作，继续遍历nums1[i+1]，并将tempstack中的元素移回mystack中

创建栈：Stack<Integer> mystack = new Stack<>();
栈顶元素：mystack.peek();
栈顶元素弹出：mystack.pop();
栈是否为空：mystack.isEmpty();
加入栈：mystack.push();
时间复杂度O(N)
空间复杂度O(N)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
        int[] result = new int[nums1.length];
        Stack<Integer> mystack = new Stack<>();
        Stack<Integer> tempstack = new Stack<>();

        for(int i = 0; i<nums2.length; i++){
            mystack.push(nums2[i]);
        }

        for(int i = 0; i <nums1.length; i++){
            boolean sig = true;
            int max = -1;
            while(sig && !mystack.isEmpty()){
                if(nums1[i] < mystack.peek()){
                    max = mystack.peek();
                }
                else if(nums1[i] == mystack.peek()){
                    sig = false;
                    while(!tempstack.isEmpty()){
                        mystack.push(tempstack.pop());
                    }
                    continue;
                }
                tempstack.push(mystack.pop());
            }
            result[i] = max;
           
        }
        return result;
    }
}