ตรวจสอบว่าอาร์เรย์เรียงลำดับได้ด้วย Stack หรือไม่ใน C++

สมมติว่าเรามีอาร์เรย์ nums ที่มีสมาชิกไม่ซ้ำกันจาก 1 ถึง n เราต้องตรวจสอบว่ามันเป็น stack-sortable หรือไม่ อาร์เรย์เรียกว่า stack-sortable เมื่อสามารถจัดเก็บไว้ในอีกอาร์เรย์หนึ่งโดยใช้ stack ชั่วคราวได้

เราสามารถใช้การดำเนินการเหล่านี้กับอาร์เรย์ได้:

• ลบสมาชิกแรกของอาร์เรย์และ push เข้า stack
• ลบสมาชิกบนสุดของ stack และเพิ่มเข้าไปที่ท้ายอาร์เรย์ที่สอง

ถ้าสมาชิกทั้งหมดของอาร์เรย์เดิมถูกโอนไปยังอาร์เรย์ที่สองด้วยการดำเนินการเหล่านี้ จนอาร์เรย์ที่สองเรียงลำดับจากน้อยไปมาก (non-decreasing) แสดงว่าอาร์เรย์เดิมเป็น stack-sortable

เช่น ถ้าอินพุตคือ nums = [8, 6, 5, 3, 1] ผลลัพธ์จะเป็น True เพราะเราสามารถหมุนสองครั้งตามเข็มนาฬิกาได้ แล้วจะเรียงเป็น [1, 3, 4, 5, 6, 8]

วิธีแก้ปัญหา

• สร้าง stack stk
• last := 0
• ลูป i := 0 ถึง i < ขนาดของ v เพิ่ม i ทีละ 1:
  • ถ้า stk ไม่ว่าง:
    • top := top element of stk
    • while top == last + 1:
      • last := last + 1
      • pop จาก stk
      • ถ้า stk ว่าง: ออกจากลูป
      • top := top element of stk
    • ถ้า stk ว่าง: push v[i] เข้า stk
    • มิฉะนั้น:
      • top := top element of stk
      • ถ้า v[i] < top: push v[i] เข้า stk
      • มิฉะนั้น: คืนค่า false
  • มิฉะนั้น: push v[i] เข้า 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;
}

int main(){
    vector<int> v = {8, 6, 5, 3, 1};
    cout << solve(v);
}

Input

{8, 6, 5, 3, 1}

Output

1