检查数组是否可进行堆栈排序

给定一个由N个不同元素组成的数组，其中元素介于1和N之间（两者都包含），请检查它是否可堆栈排序。如果可以使用临时堆栈S将数组A[]存储在另一个数组B[]中，则称其为堆栈可排序。

阵列上允许的操作包括：

1. 移除数组A[]的起始元素并将其推入堆栈。
2. 移除堆栈S的顶部元素，并将其附加到数组B的末尾。

如果可以通过执行这些操作将A[]的所有元素移动到B[]，从而使数组B按升序排序，那么数组A[]是可堆栈排序的。

例如：

Input : A[] = { 3, 2, 1 }
Output : YES
Explanation : 
Step 1: Remove the starting element of array A[] 
        and push it in the stack S. ( Operation 1)
        That makes A[] = { 2, 1 } ; Stack S = { 3 }
Step 2: Operation 1
        That makes A[] = { 1 } Stack S = { 3, 2 }
Step 3: Operation 1
        That makes A[] = {} Stack S = { 3, 2, 1 }
Step 4: Operation 2
        That makes Stack S = { 3, 2 } B[] = { 1 }
Step 5: Operation 2
        That makes Stack S = { 3 } B[] = { 1, 2 }
Step 6: Operation 2
        That makes Stack S = {} B[] = { 1, 2, 3 }
  
Input : A[] = { 2, 3, 1}
Output : NO

给定数组A[]是[1，…，N]的置换，所以让我们假设最初的B[]={0}。现在我们可以观察到：

1. 我们只能在堆栈为空或当前元素小于堆栈顶部时，推送堆栈中的元素。
2. 只有当堆栈顶部是空的，我们才能从堆栈中弹出 因为数组B[]将包含{1,2,3,4，…，n}。

   如果我们不能将数组A[]的起始元素推入，那么给定的数组就不能进行堆栈排序。

   以下是上述理念的实施：

   C++

   // C++ implementation of above approach. #include <bits/stdc++.h> using namespace std; // Function to check if A[] is // Stack Sortable or Not. bool check( int A[], int N) { // Stack S stack< int > S; // Pointer to the end value of array B. int B_end = 0; // Traversing each element of A[] from starting // Checking if there is a valid operation // that can be performed. for ( int i = 0; i < N; i++) { // If the stack is not empty if (!S.empty()) { // Top of the Stack. int top = S.top(); // If the top of the stack is // Equal to B_end+1, we will pop it // And increment B_end by 1. while (top == B_end + 1) { // if current top is equal to // B_end+1, we will increment // B_end to B_end+1 B_end = B_end + 1; // Pop the top element. S.pop(); // If the stack is empty We cannot // further perfom this operation. // Therefore break if (S.empty()) { break ; } // Current Top top = S.top(); } // If stack is empty // Push the Current element if (S.empty()) { S.push(A[i]); } else { top = S.top(); // If the Current element of the array A[] // if smaller than the top of the stack // We can push it in the Stack. if (A[i] < top) { S.push(A[i]); } // Else We cannot sort the array // Using any valid operations. else { // Not Stack Sortable return false ; } } } else { // If the stack is empty push the current // element in the stack. S.push(A[i]); } } // Stack Sortable return true ; } // Driver's Code int main() { int A[] = { 4, 1, 2, 3 }; int N = sizeof (A) / sizeof (A[0]); check(A, N)? cout<< "YES" : cout<< "NO" ; return 0; }

   JAVA

   // Java implementation of above approach. import java.util.Stack; class GFG { // Function to check if A[] is // Stack Sortable or Not. static boolean check( int A[], int N) { // Stack S Stack<Integer> S = new Stack<Integer>(); // Pointer to the end value of array B. int B_end = 0 ; // Traversing each element of A[] from starting // Checking if there is a valid operation // that can be performed. for ( int i = 0 ; i < N; i++) { // If the stack is not empty if (!S.empty()) { // Top of the Stack. int top = S.peek(); // If the top of the stack is // Equal to B_end+1, we will pop it // And increment B_end by 1. while (top == B_end + 1 ) { // if current top is equal to // B_end+1, we will increment // B_end to B_end+1 B_end = B_end + 1 ; // Pop the top element. S.pop(); // If the stack is empty We cannot // further perfom this operation. // Therefore break if (S.empty()) { break ; } // Current Top top = S.peek(); } // If stack is empty // Push the Current element if (S.empty()) { S.push(A[i]); } else { top = S.peek(); // If the Current element of the array A[] // if smaller than the top of the stack // We can push it in the Stack. if (A[i] < top) { S.push(A[i]); } // Else We cannot sort the array // Using any valid operations. else { // Not Stack Sortable return false ; } } } else { // If the stack is empty push the current // element in the stack. S.push(A[i]); } } // Stack Sortable return true ; } // Driver's Code public static void main(String[] args) { int A[] = { 4 , 1 , 2 , 3 }; int N = A.length; if (check(A, N)) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } //This code is contributed by PrinciRaj1992

   输出：

   YES
   

   时间复杂性 ：O（N）。