C++ 中的下一个更大元素 II
c++server side programmingprogramming
假设我们有一个循环数组(最后一个元素的下一个元素是数组的第一个元素)，我们需要为每个元素显示下一个更大值。这里，数字 x 的下一个更大值是数组中按遍历顺序排列的第一个更大值，这意味着我们可以循环查找它的下一个更大值。如果不存在，则值为 -1。因此，如果数字为 [1, 2, 1, 3, 2, 1]，则输出为:[2,3,3,-1,3,2]
为了解决这个问题，我们将遵循以下步骤 −
- n := 数组大小
- 定义一个名为 res 的数组，大小为 n，并用 -1 填充，定义一个堆栈 st
- i 在 0 到 2n 的范围内
- index := i mod n, x := nums[index]
- 当 st 非空且 nums[栈顶] < x
- res[栈顶] := x
- 从堆栈中删除顶部元素
- 将索引插入堆栈
- return res
示例(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]
