Kiểm tra mảng có thể sắp xếp bằng stack trong C++

Giả sử chúng ta có một mảng nums chứa các phần tử duy nhất từ 1 đến n. Chúng ta phải kiểm tra xem nó có thể sắp xếp bằng stack (stack-sortable) hay không. Một mảng có thể sắp xếp bằng stack khi nó có thể được lưu trữ trong một mảng khác sử dụng một stack tạm thời.

Để giải quyết vấn đề này, chúng ta có thể sử dụng bất kỳ phép toán nào sau đây trên mảng:

Xóa phần tử đầu tiên của mảng và đẩy phần tử đó vào stack.
Xóa phần tử đỉnh của stack và chèn nó vào cuối mảng thứ hai.

Bây giờ nếu tất cả các phần tử của mảng cho trước được chuyển sang mảng thứ hai bằng các phép toán này sao cho mảng thứ hai được sắp xếp theo thứ tự không giảm, thì mảng cho trước là có thể sắp xếp bằng stack.

Vì vậy, nếu đầu vào giống như nums = [8, 6, 5, 3, 1], thì đầu ra sẽ là True vì chúng ta có thể xoay hai lần theo chiều kim đồng hồ thì nó sẽ được sắp xếp như [1, 3, 4, 5, 6, 8].

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:

Định nghĩa một stack stk
last := 0
Với i := 0, khi i < kích thước của v, tăng i lên 1, làm:
- Nếu stk không rỗng, thì:
  - top := phần tử đỉnh của stk
  - Khi top bằng (last + 1), làm:
    - last := last + 1
    - Pop từ stk
    - Nếu stk rỗng, thì:
      - Thoát khỏi vòng lặp
    - top := phần tử đỉnh của stk
  - Nếu stk rỗng, thì:
    - Đẩy v[i] vào stk
  - Ngược lại:
    - top := phần tử đỉnh của stk
    - Nếu v[i] < top, thì:
      - Đẩy v[i] vào stk
    - Ngược lại:
      - Trả về false
- Ngược lại:
  - Đẩy v[i] vào stk
Trả về true

Ví dụ mã

#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);
    return 0;
}

Đầu vào

{8, 6, 5, 3, 1}

Kiểm tra mảng có thể sắp xếp bằng stack trong C++

Ví dụ mã

Đầu vào

Đầu ra