配列がC++でスタックソート可能かどうかを確認します

1からnまでの一意の要素の配列numがあるとします。スタックソート可能かどうかを確認する必要があります。配列は、一時スタックを使用して他の配列に格納できる場合、スタックソート可能です。

これを解決するために、配列でこれらの操作のいずれかを使用できます-

• 配列の開始要素を削除し、そのアイテムをスタックにプッシュします。

• スタックの一番上の要素を削除し、2番目の配列の最後に挿入します。

これで、指定された配列のすべての要素がこれらの操作によって2番目の配列に転送され、2番目の配列が降順ではない順序で並べ替えられる場合、指定された配列はスタック並べ替え可能です。

したがって、入力がnums =[8、6、5、3、1]の場合、時計回りに2回回転できるため、出力はTrueになり、[1、3、4、 5、6、8]

これを解決するには、次の手順に従います-

• 1つのスタックスタックを定義する
• 最後：=0
• iを初期化する場合：=0、i
• stkが空でない場合、-
  • top：=stkの最上位要素
  • topは（last + 1）と同じですが、-
    を実行します。
    • 最後：=最後+1
    • stkからポップ
    • stkが空の場合、次のようになります。
      • ループから抜け出す
    • top：=stkの最上位要素
  • stkが空の場合、次のようになります。
    • v[i]をstkにプッシュ
  • それ以外の場合
    • top：=stkの最上位要素
    • v [i]
    • v[i]をstkにプッシュ
  • それ以外の場合
    • falseを返す

理解を深めるために、次の実装を見てみましょう-

例

#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