数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中检查数组是否可堆栈排序
假设我们有一个数组 nums，其中包含从 1 到 n 的唯一元素。我们必须检查它是否可堆栈排序。当数组可以使用临时堆栈存储到另一个数组中时，该数组即可堆栈排序。
为了解决这个问题，我们可以对数组执行以下任何操作：
删除数组的起始元素并将该元素压入堆栈。
删除堆栈的顶部元素并将其插入到第二个数组的末尾。
现在，如果通过这些操作将给定数组的所有元素都转移到第二个数组，则第二个数组按非递减顺序排序，则给定数组即可堆栈排序。
因此，如果输入类似于 nums = [8, 6, 5, 3, 1]，则输出将为 True，因为我们可以顺时针旋转两次，然后它将按 [1, 3, 4, 5, 6, 8] 排序。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个堆栈 stk
- last := 0
- for i := 0, i < v 的大小, i := i + 1:
- 如果 stk 不为空，则：
- top := stk 的顶部元素
- while top == (last + 1):
- last := last + 1
- 从 stk 中弹出
- 如果 stk 为空，则
- 退出循环
- top := stk 的顶部元素
- 如果 stk 为空，则
- 将 v[i] 压入 stk
- 否则
- top := stk 的顶部元素
- 如果 v[i] < top，则
- 将 v[i] 压入 stk
- 否则
- 返回 false
- 否则
- 将 v[i] 压入 stk
- 如果 stk 不为空，则：
- 返回 true
让我们看看下面的实现以更好地理解：
示例
#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
更新于：2020-12-30
233 次浏览
广告