C++에서 배열이 스택 정렬 가능한지 확인

<시간/>

1에서 n까지의 고유한 요소의 배열 번호가 있다고 가정합니다. 스택 정렬 가능 여부를 확인해야 합니다. 배열은 임시 스택을 사용하여 다른 배열에 저장할 수 있을 때 스택 정렬이 가능합니다.

이 문제를 해결하기 위해 배열에서 다음 작업 중 하나를 사용할 수 있습니다. −

배열의 시작 요소를 삭제하고 해당 항목을 스택에 푸시합니다.
스택의 맨 위 요소를 삭제하고 두 번째 배열의 끝에 삽입합니다.

이제 주어진 배열의 모든 요소가 이러한 작업에 의해 두 번째 배열로 전송되어 두 번째 배열이 내림차순으로 정렬되지 않으면 주어진 배열은 스택 정렬이 가능합니다.

따라서 입력이 nums =[8, 6, 5, 3, 1]과 같으면 시계 방향으로 두 번 회전할 수 있으므로 출력은 True가 됩니다. 그러면 [1, 3, 4, 5, 6, 8]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 스택 stk 정의
마지막 :=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로 푸시
  - 그렇지 않으면
    - 거짓 반환
그렇지 않으면
- v[i]를 stk로 푸시

참을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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}