数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的循环数组的下一个较大元素
假设我们有一个循环数组（最后一个元素的下一个元素是该数组的第一个元素），我们必须显示每个元素的下一个较大数字。此处的某个数 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
- 删除栈顶元素
- 将 index 插入栈
- 返回 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]
更新于: 2020 年 4 月 29 日
185 次观看
广告