LC 503. 下一个更大元素 II

题目描述

这是 LeetCode 上的 503. 下一个更大元素 II ，难度为 中等。

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。

数字 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$

---

单调栈

对于「找最近一个比当前值大/小」的问题，都可以使用单调栈来解决。

单调栈就是在栈的基础上维护一个栈内元素单调。

在理解单调栈之前，我们先回想一下「朴素解法」是如何解决这个问题的。

对于每个数而言，我们需要遍历其右边的数，直到找到比自身大的数，这是一个 $O(n^2)$ 的做法。

之所以是 $O(n^2)$，是因为每次找下一个最大值，我们是通过「主动」遍历来实现的。

而如果使用的是单调栈的话，可以做到 $O(n)$ 的复杂度，我们将当前还没得到答案的下标暂存于栈内，从而实现「被动」更新答案。

也就是说，栈内存放的永远是还没更新答案的下标。

具体的做法是：

每次将当前遍历到的下标存入栈内，将当前下标存入栈内前，检查一下当前值是否能够作为栈内位置的答案（即成为栈内位置的「下一个更大的元素」），如果可以，则将栈内下标弹出。

如此一来，我们便实现了「被动」更新答案，同时由于我们的弹栈和出栈逻辑，决定了我们整个过程中栈内元素单调。

还有一些编码细节，由于我们要找每一个元素的下一个更大的值，因此我们需要对原数组遍历两次，对遍历下标进行取余转换。

以及因为栈内存放的是还没更新答案的下标，可能会有位置会一直留在栈内（最大值的位置），因此我们要在处理前预设答案为 -1。而从实现那些没有下一个更大元素（不出栈）的位置的答案是 -1。

Java 代码：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n * 2; i++) {
            while (!d.isEmpty() && nums[i % n] > nums[d.peekLast()]) {
                int u = d.pollLast();
                ans[u] = nums[i % n];
            }
            d.addLast(i % n);
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        deque<int> d;
        for (int i = 0; i < n * 2; i++) {
            while (!d.empty() && nums[i % n] > nums[d.back()]) {
                int u = d.back();
                d.pop_back();
                ans[u] = nums[i % n];
            }
            d.push_back(i % n);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        d = deque()
        for i in range(n * 2):
            while d and nums[i % n] > nums[d[-1]]:
                u = d.pop()
                ans[u] = nums[i % n]
            d.append(i % n)
        return ans

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

数组模拟栈

本题不需要用到这个技巧，但是还是介绍一下，可作为拓展。

我们可以使用静态数组来模拟栈，这样我们的代码将会更快一点：

Java 代码：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        // 使用数组模拟栈，hh 代表栈底，tt 代表栈顶
        int[] d = new int[n * 2];
        int hh = 0, tt = -1;
        for (int i = 0; i < n * 2; i++) {
            while (hh <= tt && nums[i % n] > nums[d[tt]]) {
                int u = d[tt--];
                ans[u] = nums[i % n];
            }
            d[++tt] = i % n;
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        vector<int> d(n * 2);
        int hh = 0, tt = -1;
        for (int i = 0; i < n * 2; i++) {
            while (hh <= tt && nums[i % n] > nums[d[tt]]) {
                int u = d[tt--];
                ans[u] = nums[i % n];
            }
            d[++tt] = i % n;
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        d = [0] * (n * 2)
        hh, tt = 0, -1
        for i in range(n * 2):
            while hh <= tt and nums[i % n] > nums[d[tt]]:
                ans[d[tt]] = nums[i % n]
                tt -= 1
            tt += 1
            d[tt] = i % n
        return ans

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

总结

要从逻辑上去理解为什么能用「单调栈」解决问题：

1. 我们希望将 $O(n^2)$ 算法优化为 $O(n)$ 算法，因此需要将「主动」获取答案转换为「被动」更新
2. 我们需要使用数据结构保持那些「尚未更新」的位置下标，由于题目要求的是找「下一个更大的元素」，因此使用栈来保存
3. 「被动」更新答案的逻辑导致了我们栈内元素单调

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.501 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。