LeetCode503-下一个更大元素II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/next-greater-element-ii/

中文链接：https://leetcode-cn.com/problems/next-greater-element-ii/

题目详述

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

示例 1:

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

注意: 输入数组的长度不会超过 10000。

题目详解

  • 与 LeetCode496-下一个更大元素I 类似，区别在于将线性数组升级为了循环数组。解答思路是一致的，仍旧是运用单调栈。
  • 将原数组拼接一份放在数组后面得到一个新的数组。可以进行物理拼接，即创建一个新的数组，也可以进行逻辑拼接，超过原数组的长度的下标进行转换。这样就把循环数组的问题转化为了线性数组的问题。
  • 创建一个结果数组，所有元素赋值为 -1.
  • 遍历逻辑数组，运用单调栈进行结算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00503 {

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int len = (n << 1) - 1;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; ++i) {
            int t = i < n ? i : i - n;
            while (!stack.isEmpty() && nums[t] > nums[stack.peek()]) {
                res[stack.pop()] = nums[t];
            }
            stack.push(t);
        }
        return res;
    }
}
  • 可以进行对上面的代码进行一些小优化。
  • 优化一：当 i 小于 n 时，才 push 进栈；否则不用入栈。
  • 优化二：栈中剩余的索引就是那些不存在下一个更大元素的元素的索引，可以逐个 pop 并赋值对应位置为 -1，这样结果数组中元素可以不用事先实现初始化为 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00503 {

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int len = (n << 1) - 1;
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; ++i) {
            int x = nums[i < n ? i : i - n];
            while (!stack.isEmpty() && x > nums[stack.peek()]) {
                res[stack.pop()] = x;
            }
            // n 之前的才 push 进栈
            if (i < n) {
                stack.push(i);
            }
        }
        // 栈中剩余的索引就是那些不存在下一个更大元素的元素的索引
        while (!stack.isEmpty()) {
            res[stack.pop()] = -1;
        }
        return res;
    }
}