域名注册管理中心网站,百度号码认证,网站开发大数据库,建立免费网站的步骤1. 题意
在一个循环数组中#xff0c;找到下一个比它大的数。
2. 题解
也不知道怎么就单调栈了#xff0c;可能是刷出来的吧。。。
还是来解释一下吧#xff01;#xff01;#xff01;
如果有新元素入栈 c c c#xff0c;
那么在栈内的元素只要小于新元素的 s s s…1. 题意
在一个循环数组中找到下一个比它大的数。
2. 题解
也不知道怎么就单调栈了可能是刷出来的吧。。。
还是来解释一下吧
如果有新元素入栈 c c c
那么在栈内的元素只要小于新元素的 s s s都需要出栈因为他们的
下一个更大的元素显然就是 c c c。这些小于 s s 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 大于栈顶元素44出栈且它的下一个比它大的元素就是5
s: 6
5 小于栈顶元素65入栈
s:6 5
3 小于栈顶元素53入栈
s:6 5 3
1 小于栈顶元素31入栈
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:vectorint nextGreaterElements(vectorint nums) {int n nums.size(); std::stackint s;vectorint 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:vectorint nextGreaterElements(vectorint nums) {int n nums.size(); std::stackint s;vectorint 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;}
};
