1. 題意

在一個循環數組中，找到下一個比它大的數。

2. 題解

也不知道怎么就單調棧了，可能是刷出來的吧。。。

還是來解釋一下吧！！！

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

那么在棧內的元素只要小于新元素的$s$，都需要出棧，因為他們的

下一個更大的元素顯然就是$c$。這些小于$s$的棧內元素都需要出棧。

更進一步的說，棧內的元素它們都還沒有找到下一個更大的元素。

為什么是棧呢？因為我們先比較的是離當前元素最近的，

也就是后入棧的那些先比較，也就滿足了先進后出的特性。

那么單調性呢？因為在入棧時需要保證棧內元素是小于當前元素的，因

此棧內元素一定是單調遞減的，當然可以相等。

舉個例子

6 4 2 5 3 1s:
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;}
};