判断栈的输出序列是否合法（一）
判断栈的输出序列是否合法
（一） 检查数列的局部单调性
我们先给出这样的一个结论
凡是合法的出栈序列，每个数后面的比它小的数，必然是按递减次序排列的。
为了证明这个结论，我们可以将入栈元素按入栈顺序由1到n进行编号，对于入栈序列1到n，第x个元素入栈时，那么前x-1个数一定已经全部入栈。则当第x个数出栈时，栈中若剩余编号小于x元素，则这些元素一定在存储器中倒序排列。
这个结论还可以用更加严谨的过程来证明，即假设在出栈过程中的某一个步骤时，栈中存留的元素有n个，分别是S1到Sn。
此时，对于元素 Sn，有两种可能性。
- 在下一步时，可以选择弹出Sn。那么，比Sn小的所有元素，只有两种可能：
a. 还未出栈（不可能还未入栈，因为比它大的元素Sn已经入栈了）：则一定在Sn后以递减的顺序出现在出栈队列中（因为入栈的顺序是严格递增的）
b. 已经出栈：此时，比这个元素还小的元素如果还没出栈，当它即将出栈的时候，就会又递归回到1）的情况。
- 可以不弹出Sn而是继续入栈，则又回到 1）的情况。
因此，我们得出这样的结论：凡是合法的出栈序列，每个数后面的比它小的数，必然是按递减次序排列的。
利用这个理论，我们可以较快地判断所含元素较少的栈的输出序列是否合法。
在算法实现方面，我们新建数组A存储序号x之前的元素，并扫描数组A以验证其是否逆序。该算法时间复杂度为O（n²）
具体程序如下：
#include<bits/stdc++.h>
using namespace std;
int n, t;
bool checkValidOrder(int *q,int p)
{
int* A = new int[n];
int x(0);
for (int i = p + 1; i < n; i++)
if (q[i] < q[p]) A[x++] = q[i];
for (int i = 0; i < x; i++)
if (A[i] < A[i - 1]) return false;
return true;
delete[] A;
}
int main() {
cin >> n;
int *Q=new int[n];
for (int j = 0; j < n; j++) {
cin >> t;
Q[j]=t;
}
for (int i = 0; i < n - 1; i++)
if (!checkValidOrder(Q, i)) {
cout << "No";
break;
}
else cout << "Yes";
delete[] Q;
}