下一个更大元素2

发表于 分类于 阅读次数：

下一个更大元素2（难度：中等）

1

方法：单调栈

思路

转自：

作者：labuladong 链接：https://leetcode-cn.com/problems/next-greater-element-ii/solution/dan-diao-zhan-jie-jue-next-greater-number-yi-lei-2/ 来源：力扣（LeetCode）

同样是 Next Greater Number，现在假设给你的数组是个环形的，如何处理？

首先，计算机的内存都是线性的，没有真正意义上的环形数组，但是我们可以模拟出环形数组的效果，一般是通过 % 运算符求模（余数），获得环形特效：

1
2
3
4
5
6
int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
    print(arr[index % n]);
    index++;
}

回到 Next Greater Number 的问题，增加了环形属性后，问题的难点在于：这个 Next 的意义不仅仅是当前元素的右边了，有可能出现在当前元素的左边。

我们可以考虑这样的思路：将原始数组 “翻倍”，就是在后面再接一个原始数组，这样的话，按照之前“比身高”的流程，每个元素不仅可以比较自己右边的元素，而且也可以和左边的元素比较了。

ink-image (2)

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[nums.length];

        for(int i = 2*n-1; i >= 0; i--){ // i从2*n-1开始
            while(!stack.empty() && stack.peek() <= nums[i%n]){
                stack.pop();
            }
            res[i%n] = stack.empty() ? -1 : stack.peek();
            stack.push(nums[i%n]);
        }
        return res;
    }
}
2