数据结构的一道题求大神解救

C 栈 数据结构 C++ 测试

Description
小明很喜欢玩射击游戏。他刚考完了数据结构期末考试，感觉不错，于是又来到了射击娱乐场放松一下。和上次一样，先从老板那租了一把步枪和装有N发子弹的弹夹。这里，再把规则说一遍。在射击的过程中，小明每次都有两种选择：从弹夹中取出一颗子弹上膛，或者打一发子弹出去。注意：所有的子弹都从枪口上膛。小明感觉这有点像《数据结构》课程中的“栈”的特点。因此在打完了这N发子弹之后，他想验证一下这些子弹打出来的顺序是不是真的满足“栈”的特性。假设N颗子弹的编号为1,2,…,N。子弹从弹夹中取出的顺序也是从1到N，这里N = 10。给定一个子弹被打出的顺序，你可以帮小明验证它满不满足“栈”的打出顺序吗？
Input
可能有多个测试输入，第一行给出总共的测试输入的个数。
每个测试输入只有一行：用空格隔开的十个数，表示子弹打出的编号顺序。
Output
对每个测试输入，输出只有一行：
“Yes”，如果打出顺序满足“栈”的特点；
“No”，如果打出顺序不满足“栈”的特点。
Sample Input
3
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
3 1 2 4 5 6 7 8 9 10
Sample Output
Yes
Yes
No

这是我的代码，为什么WA啊？求救啊

#include <iostream>
#include <stack>
using namespace std;

int main() {
	int a[10], n = 0, i = 0, j = 0;
	bool k = true;
	stack<int> s[10];
	cin >> n;
	while (n--) {
		for (i = 0; i < 10; i++) {
			cin >> a[i];
		}
		for (i = 0; i < 10; i++) {
			if (i > 0) {
				if (a[i] - a[i - 1]) {
					j++;
				}
			}
			s[j].push(a[i]);
		}
		j = 0;
		for (i = 0; i < 10; i++) {
			if (s[j].empty()) {
				j++;
			}
			if (i + 1 != s[j].top()) {
				k = false;
			}
			s[j].pop();
		}
		if (k == true) {
			cout << "Yes\n";
		} else {
			cout << "No\n";
		}
		j = 0, k = true;
	}
	return 0;
}

4 个解决方案

#1

和我想象中的解法完全不同。你得解释为什么你觉得这个代码是对的。

#2

提出错了。输入必须是1到10，否则编号有什么用？

#3

一道经典面试题哦：如果“给定的出栈序列”是一个可能的序列，则必需在某种入栈方式下（要保证入栈的先后顺序是1～N），出栈序列的下一个元素是栈顶

bool isPossible(int popSequence[], int N)
{
    int n = 1, nextToPopOut;
    stack<int> st;
    
    for(nextToPopOut = 0; nextToPopOut < N; ++nextToPopOut){
        while(st.empty() || st.top() != popSequence[nextToPopOut]){
            if(n > N) return false;//1～N已经全部入栈过一次了，但是仍不能满足出栈顺序
            st.push(n++);
        }
        //能运行到这里必然有st.top() = popSequence[nextToPopOut]了
        st.pop();
    }
    return true;
}

#4

做程序员的小明果然比上学的小明聪明