下一个更大元素II

发表于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode每日一题，503. Next Greater Element II

先看题目描述

6n8rnO.png

给定一个循环数组 nums，让我们输出 nums 中每个元素的下一个更大元素，若没有更大元素则输出 -1

算法和思路

单调栈

可以使用单调栈来解决本题，单调栈中存储的是数组中元素的下标，从栈底到栈顶的下标在 nums 中对应的元素是单调不升的

遍历数组 nums，遍历到元素 nums[i] 时，若栈顶的下标对应元素小于 nums[i]，则不断弹出栈顶下标直至栈为空或栈顶下标对应元素不小于 nums[i]，这时就将 i 插入栈顶，弹出下标对应值的下一个更大元素就是 nums[i]

最后遍历完 nums 时，栈不为空，其中存储下标对应的元素要么就是找不到下一个更大元素，要么就是下一个更大元素在其前面。若是找不到下一个更大元素，则令其在结果数组中对应值为 -1 即可；否则，就从 nums 中第一个元素起开始找比它大的元素

算法源码

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int max = 0;
        int[] ans = new int[len];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                ans[stack.pop()] = num;
            }
            if (stack.isEmpty()) {
                max = num;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int cur = nums[stack.peek()];
            if (cur < max) {
                for (int num : nums) {
                    if (num > cur) {
                        ans[stack.pop()] = num;
                        break;
                    }
                }
            } else {
                ans[stack.pop()] = -1;
            }
        }
        return ans;
    }
}

下面是题解的单调栈的方法的代码，和我的方法有一些不同，对于遍历一次 nums 数组后单调栈中剩余的下标，题解中代码是采取了再遍历一次 nums 数组的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < 2 * len; i++) {
            int num = nums[i % len];
            if (!stack.isEmpty()) {
                while (!stack.isEmpty() && nums[stack.peek()] < num) {
                    ans[stack.pop()] = num;
                }
            }
            stack.push(i % len);
        }
        return ans;
    }
}