1051PopSequence(25分)java题解

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO

题目描述：

给定一个最多能保存M个数字的堆栈。按1、2、3、...、N的顺序压入N个数字，然后随机弹出。
你应该知道给定的数字序列是否可能是堆栈的弹出序列。例如，如果M是5，N是7，我们可以从堆栈获得1、2、3、4、5、6、7，而不是3、2、1、7、5、6、4。
输入规格：
每个输入文件包含一个测试用例。
对于每种情况，第一行包含3个数字(都不超过1000)：M(堆栈的最大容量)、N(推送序列的长度)和K(要检查的POP序列的数量)。
然后是K行，每行都包含一个由N个数字组成的弹出序列。
一行中的所有数字都用空格分隔。
输出规格：
对于每个弹出序列，如果确实是堆栈的可能弹出序列，则在一行中打印“yes”，如果不是，则打印“no”。

解题思路：

题目大意为在限定一个栈容量的情况下，判断可能的出栈序列。

可以实时模拟栈的进出情况，栈的初始栈顶为第一个数据的值，之后元素如果是栈顶就弹出，如果是新入栈的元素，则让栈顶继续为新元素（需要用while判断入栈）。

注意判断的下一个数据不一定是栈顶的下一个元素，还可能有跳跃情况，例如 3 6 7 5 4 2 1从3到6

java代码：

import java.io.*;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int capacity = Integer.parseInt(split[0]);//栈容量
int rage = Integer.parseInt(split[1]);//入栈的最大值
int n = Integer.parseInt(split[2]);//数据量

String[]str = new String[n];
for(int i = 0; i str[i] = br.readLine();
}
for(int i = 0; i int k = 1;
Stack stack = new Stack();
split = str[i].split(" ");
int temp = Integer.parseInt(split[0]);//第一个数据
while(k <= temp && stack.size() stack.push(k);
k++;
}
stack.pop();//如果没超出栈容量，则第一个元素顺利出栈
int j;
for(j = 1; j int x = Integer.parseInt(split[j]);
if(x >= k || (!stack.isEmpty() && x == stack.peek())) {
if(x >= k) {//可能有跳跃情况 3 6 7 5 4 2 1 从3到6
while(k <= x && stack.size() stack.push(k);
k++;
}
stack.pop();
}else {
stack.pop();//栈顶元素弹出
}
}else {//不是弹的栈顶
System.out.println("NO");
break;
}
}
if(j == rage) {//执行顺利，中途没有break
System.out.println("YES");
}
}
}
}

PAT提交截图：