检查数组在C ++中是否可以堆栈排序
假设我们有一个从1到n的唯一元素数组。我们必须检查它是否可以堆栈排序。当一个数组可以使用临时堆栈存储在其他数组中时，该数组是可排序的。
为了解决这个问题，我们可以在数组上使用以下任何操作：
删除数组的起始元素，然后将该项目推入堆栈。
删除堆栈的顶部元素，并将其插入第二个数组的末尾。
现在，如果通过这些操作将给定数组的所有元素转移到第二个数组，因此第二个数组以非降序排序，则给定数组是可堆栈排序的。
因此，如果输入类似于nums = [8、6、5、3、1]，那么输出将为True，因为我们可以沿顺时针方向旋转两次，然后将其排序为[1、3、4， 5、6、8]
为了解决这个问题，我们将遵循以下步骤-
定义一个堆栈stk
最后：= 0
对于初始化i：= 0，当i <v的大小时，更新（将i增加1），执行-
将v [i]推入stk
top：= stk的顶部元素
当top与（last + 1）相同时，执行-
如果stk为空，则：
除此以外
从循环中出来
最后：=最后+ 1
从stk弹出
如果stk为空，则：
top：= stk的顶部元素
将v [i]推入stk
返回假
将v [i]推入stk
top：= stk的顶部元素
如果v [i] <top，则：
除此以外
如果stk不为空，则-
除此以外
返回真
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>using namespace std;
bool solve(vector<int> &v) {
stack<int> stk;
int last = 0;
for (int i = 0; i < v.size(); i++) {
if (!stk.empty()){
int top = stk.top();
while (top == last + 1) {
last = last + 1;
stk.pop();
if (stk.empty()){
break;
} top = stk.top();
}
if (stk.empty()) {
stk.push(v[i]);
}else{
top = stk.top();
if (v[i] < top){
stk.push(v[i]);
}else{
return false;
}
}
}else{
stk.push(v[i]);
}
} return true;
}main(){
vector<int>
v = {8, 6, 5, 3, 1};
cout << solve(v);
}
输入值
{8, 6, 5, 3, 1}输出结果1
以上是 检查数组在C ++中是否可以堆栈排序 的全部内容， 来源链接： utcz.com/z/361388.html
