資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告