leetcode_503 下一个更大元素

1. 题意

在一个循环数组中，找到下一个比它大的数。

2. 题解

也不知道怎么就单调栈了，可能是刷出来的吧。。。

还是来解释一下吧！！！

如果有新元素入栈$c$，

那么在栈内的元素只要小于新元素的$s$，都需要出栈，因为他们的

下一个更大的元素显然就是$c$。这些小于$s$的栈内元素都需要出栈。

更进一步的说，栈内的元素它们都还没有找到下一个更大的元素。

为什么是栈呢？因为我们先比较的是离当前元素最近的，

也就是后入栈的那些先比较，也就满足了先进后出的特性。

那么单调性呢？因为在入栈时需要保证栈内元素是小于当前元素的，因

此栈内元素一定是单调递减的，当然可以相等。

举个例子

6 4 2 5 3 1

s:
6  栈空直接入栈
s: 6
4  小于栈顶元素6，直接入栈
s: 6 4
2 小于栈顶元素4， 直接入栈
s:6 4 2
5 大于栈顶元素2， 2 出栈，且它的下一个比它大的元素就是5
s:6 4
5 大于栈顶元素4，4出栈，且它的下一个比它大的元素就是5
s: 6
5 小于栈顶元素6，5入栈
s:6 5
3 小于栈顶元素5，3入栈
s:6 5 3
1 小于栈顶元素3，1入栈
s: 6 5 3 1

已经遍历了一遍了，但是栈中还有元素，因此我们又从头遍历

6 大于1， 1出栈，且下一个比它大的元素是6
6 大于3， 3出栈，且下一个比它大的元素是6
6 大于5， 5出栈，且下一个比它大的元素是6
6 不大于6， 6入栈
s: 6 6
后面的过程就重复上面的过程了

对于一个循环的数组，我们常常附加一个相同的数组来把它变成

线性的。在这里我们并没有直接附加，而是采取了取模这种方式。

代码其实就没有那么重要了。。。

• 正向遍历

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        
        int n = nums.size();        
        std::stack<int> s;
        vector<int> ans( n, -1);

        for (int i = 0; i < 2 * n - 1; ++i) {
            int idx = i % n;
            while (!s.empty() && nums[s.top()] < nums[ idx ]) {
                ans[ s.top() ] = nums[ idx  ];
                s.pop();
            }
            s.push( idx );
        }


        return ans;
    }
};

• 反向遍历

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        
        int n = nums.size();        
        std::stack<int> s;
        vector<int> ans( n, -1);

        for (int i = 2 * n - 1; ~i; --i) {
            int idx = i % n;

            while (!s.empty( ) && nums[ s.top()] <= nums[ idx ]) {

                s.pop();
            }
            if (!s.empty() &&　i < n) {
                ans[ idx ] = nums[s.top()];
            }
            s.push( idx );
        }

        return ans;
    }
};