北京市规划网站友情链接模板

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;}
};