【栈】Leetcode 496 下一个更大元素I

本文介绍: 【栈】Leetcode 496 下一个更大元素I

【栈】Leetcode 496 下一个更大元素I

- 解法1 两个单调栈
- 解法2

在这里插入图片描述

解法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;
    }
}