64-下一个更大元素Ⅱ

自己的做法

算法思想

同 [下一个更大元素]一样，使用单调栈。从栈顶到栈底对应元素依次增大。

不过因为最后一个元素的下一个元素是数组的第一个元素，所以要循环两遍数组，才能确定所有元素的下一个更大元素。

因为数组最后一个元素的下一个更大元素有可能就是紧挨着它左边的元素。所以需要遍历两遍数组。

并且在第二遍循环数组时，不应该再往栈中添加元素，只是单纯的比较大小。

这样，解决该题的思路是：使用一个栈indexs来存放元素索引，先获取数组长度n，创建结果列表res，初始化为n个元素，初始值为-1。 当前遍历元素的索引为index，当栈不为空且index对应元素大于栈顶元素时，就循环出栈并添加到结果列表，直到栈为空，或index对应元素小于等于栈顶元素。

然后判断是否第一次遍历，如果是，则将index入栈；否则不入栈。

算法实现

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> indexs;
        //遍历两次
        for(int i = 0; i < 2 * n - 1; i++) {
            int index = i % n;
            while (!indexs.empty() && nums[indexs.top()] < nums[index]) {
                res[indexs.top()] = nums[index];
                indexs.pop();
            }
            //判断是否是第一次遍历
            if(i < n) {
                indexs.push(index);
            }
        }
        return res;
    }
};

性能分析

时间复杂度：$O(n)$，遍历了两遍列表。

空间复杂度：$O(n)$，使用了栈来存放索引。

参考做法完全一样。