题目大意
给定一个入栈序列\([1,2,3....,n]\),判断出栈序列\([a_{1},a_{2}.....a_{n}]\)是否合法
解题思路
这道题目我们可以用一个栈与双指针结合的算法
我们设立一个指针\(j\),一开始指向的是\(a_{1}\),也就是\(j\)的初始值为\(1\)
然后我们把\(1 \sim n\)依次入栈,在入栈的过程中如果发现此时栈顶为\(a_{j}\),那就弹出栈顶,表示\(a_{j}\)顺利出栈,并将\(j\)指针后移一位(\(j++\))
到最后我们判断一下栈内是否有剩余元素,以及\(a\)序列是否全部出栈
如果满足,输出\(Yes\),反之输出\(No\)
坑点
UVa最著名的坑点就是它的输入输出
记得每个\(n\)的序列判断结束后,最后要输出个空行
代码
#include <iostream>
#include <stack>
using namespace std;
const int N = 1010;
int n, a[N];
int main()
{
while (scanf("%d", &n), n)
{
while (scanf("%d", &a[1]), a[1])
{
for (int i = 2; i <= n; i ++ )
scanf("%d", &a[i]);
stack<int> Rail; int j = 1;
for (int i = 1; i <= n; i ++ )
{
Rail.push(i);
while (!Rail.empty() && Rail.top() == a[j]) { Rail.pop(); j ++ ; }
}
puts(Rail.empty() && j == n + 1 ? "Yes" : "No");
}
puts("");
}
}