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：= i mod n，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]