当前位置:网站首页>LeetCode 503. 下一个更大元素 II

LeetCode 503. 下一个更大元素 II

2022-07-05 09:16:00 Sasakihaise_

503. 下一个更大元素 II

 

【单调栈】把最后一个元素之前的那些元素先入栈,形成环,再按照单调栈的方法遍历即可:

即对于每个元素i,把栈中比他小的元素全部出栈,此时如果栈顶还有,那么栈顶就是第一个比他大的,如果为空说明没有。最后不要忘了把元素i入栈。

class Solution {
    // 单调栈 3:15 3:24
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack = new LinkedList();
        int i, j, n = nums.length;
        for (i = n - 2; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            stack.push(nums[i]);
        }
        int[] ans = new int[n];
        for (i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                ans[i] = -1;
            } else {
                ans[i] = stack.peek();
            }
            stack.push(nums[i]);
        }
        return ans;
    }
}

 

 

原网站

版权声明
本文为[Sasakihaise_]所创,转载请带上原文链接,感谢
https://blog.csdn.net/Sasakihaise_/article/details/125585066