美文网首页
[刷题防痴呆] 0503 - 下一个更大的元素 II (Next

[刷题防痴呆] 0503 - 下一个更大的元素 II (Next

作者: 西出玉门东望长安 | 来源:发表于2022-01-15 01:25 被阅读0次

    题目地址

    https://leetcode.com/problems/next-greater-element-ii/

    题目描述

    503. Next Greater Element II
    
    Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.
    
    The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.
    
     
    
    Example 1:
    
    Input: nums = [1,2,1]
    Output: [2,-1,2]
    Explanation: The first 1's next greater number is 2; 
    The number 2 can't find next greater number. 
    The second 1's next greater number needs to search circularly, which is also 2.
    Example 2:
    
    Input: nums = [1,2,3,4,3]
    Output: [2,3,4,-1,4]
    
    

    思路

    • 单调栈. 用单调栈维护当前位置还没找到最大值的元素index列表, 从栈底到栈顶的元素单调递减.

    关键点

    • 与I的区别是环形, 因此可以拼接一遍数组来求解.

    代码

    • 语言支持:Java
    
    class Solution {
        public int[] nextGreaterElements(int[] nums) {
            Deque<Integer> stack = new ArrayDeque<>();
            int n = nums.length;
            int[] res = new int[n];
            Arrays.fill(res, -1);
            for (int i = 0; i < 2 * n; i++) {
                while (!stack.isEmpty() && nums[stack.peek() % n] < nums[i % n]) {
                    int index = stack.pop();
                    res[index % n] = nums[i % n];
                }
                stack.push(i);
            }
    
            return res;
        }
    }
    

    相关文章

      网友评论

          本文标题:[刷题防痴呆] 0503 - 下一个更大的元素 II (Next

          本文链接:https://www.haomeiwen.com/subject/dsqhcrtx.html