503.下一个更大元素II

灰太狼 2024-02-25 04:05 10阅读 0赞

#### 503.下一个更大元素II ####

*  题干分析
 *  解题思路
 *  代码实现

## 题干分析 ##

[力扣入口][Link 1]

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

*  输入: \[1,2,1\]
 *  输出: \[2,-1,2\]
 *  解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

提示:

*  1 <= nums.length <= 10^4
 *  \-10^9 <= nums\[i\] <= 10^9

## 解题思路 ##

做本题之前建议先做**739. 每日温度**和 **496.下一个更大元素 I** 。

这道题和**739. 每日温度**也几乎如出一辙。

不过，本题要循环数组了。

相信不少同学看到这道题，就想那我直接把两个数组拼接在一起，然后使用单调栈求下一个最大值不就行了！

确实可以！

将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。

这种写法确实比较直观，但做了很多无用操作，例如修改了nums数组，而且最后还要把result数组resize回去。

resize倒是不费时间，是O(1)的操作，但扩充nums数组相当于多了一个O(n)的操作。

其实也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。

## 代码实现 ##

class Solution {
        
        // 503.下一个更大元素II
        public int[] nextGreaterElements(int[] nums){
        
            //边界判断
            if(nums == null || nums.length <= 1) {
        
                return new int[]{
        -1};
            }
            int size = nums.length;
            int[] result = new int[size];//存放结果
            Arrays.fill(result,-1);//默认全部初始化为-1
            Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标
            for(int i = 0; i < 2*size; i++) {
        
                while(!st.empty() && nums[i % size] > nums[st.peek()]) {
        
                    result[st.peek()] = nums[i % size];//更新result
                    st.pop();//弹出栈顶
                }
                st.push(i % size);
            }
            return result;
        }
    }

**参考资料**：[代码随想录-503.下一个更大元素II][-503._II]

[Link 1]: https://leetcode.cn/problems/next-greater-element-ii/
[-503._II]: https://programmercarl.com/0503.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE