C ++中的下一个Greater Element II
假设我们有一个圆形数组（最后一个元素的下一个元素是数组的第一个元素），我们必须为每个元素显示下一个更大的数字。在这里，数字x的下一个更大的数字是数组中其遍历顺序中第一个更大的数字，这意味着我们可以循环搜索以找到其下一个更大的数字。如果不存在，则为-1。因此，如果数字为[1、2、1、3、2、1]，则输出将为：[2、3、3，-1、3、2]
为了解决这个问题，我们将遵循以下步骤-
n：=数组大小
定义一个称为res的数组，大小为n，并用-1填充，定义一个堆栈st
对于我在0到2n范围内
res[堆栈顶部]：=x
从堆栈中删除顶部元素
index：=imodn，x：=nums[index]
当st不为空且nums[堆栈顶部]<x
将索引插入堆栈
返回资源
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector <int> res(n, - 1);
stack <int> st;
for(int i = 0; i < 2 * n; i++){
int idx = i % n;
int x = nums[idx];
while(!st.empty() && nums[st.top()] < x){
res[st.top()] = x;
st.pop();
}
st.push(idx);
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,3,2,1};
print_vector(ob.nextGreaterElements(v));
}输入值
[1,2,1,3,2,1]
输出结果
[2,3,3,-1,3,2]