LeetCode503 下一个更大元素II

发表于 | 分类于 |
字数统计: 277 | 阅读时长 ≈ 1

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

题意

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

解法

考虑单调栈解法 但是由于需要循环数组
比较容易想到的是扩充数组，但是这样会浪费时间和空间
所以只需要取模就可以完成
算是单调栈的一个简单变种

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> greater, ans;
        int n = nums.size();
        ans.resize(n);
        for (int i = 2 * n - 1; i >= 0; i--) {
            while (greater.size() && greater.back() <= nums[i % n]) {
                greater.pop_back();
            }
            if (i < n) {
                if(greater.empty()) {
                    ans[i] = -1;
                }
                else {
                    ans[i] = greater.back();
                }
            }
            greater.push_back(nums[i % n]);
        }
        return ans;
    }
};