补充：10.10，今天想到这个算法空间复杂度其实可以更小的，甚至不需要数组来存储，我们直接使用在线处理的思想就好，用变量记下逆序列的第一个元素，在逆序列输出结束时，比较第一个元素和新输入的元素即可
问题描述
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：栈的容量
N：序列的元素数量
K：需要判断序列的数量
M,N,K<=1000
给你一个序列
让你判断所给序列是否可能是以1 2.....N的顺序压栈，然后随意时间，随意出栈元素个数所形成的序列
第一行表示：
[M N K]
2-K行
需要判断的序列
解决思路
通过仔细观察，可以得出：
所有可能的序列都有以下的特征：
1.序列最多具有N个逆序列（逆序列元素只有一个也算在其中）
2.下一个逆序列首元素大于上一个逆序列首元素（第一个不计入其中）
3.每个逆序列元素个数不能大于栈的容量M
逆序列：元素从小到大的序列
着重讲解2.3点
第二点：因为是按从小到大的顺序压栈，所以每次出栈的元素都会形成一个逆序列Q，而下一次形成逆序列K时，逆序列k的首元素都会大于逆序列Q的首元素
仔细想想，这是由于从小到大的压栈所形成特性！
第三点：因为栈的容量决定了逆序列元素的数量
Some Detail Of Function（含有写题时的思路，感想，建议结合代码阅读
existSequence：判断序列是否是可能的出栈序列
当M == 1，只能是原样输出，所以只需要遍历查看是否是1 2 3.....N
当M != 1，只要判断有不符合三个特征之一，便可以return false。
遍历比较array[step]和array[step+1]的大小，如果step > step+1 判断count是否>M+1(这里懒得写array，下同）
在这里，使用count来表示逆序列的元素数量，由于step 和 step + 1比较，所以count不能大于M-1（第三点）
如果小于，比较两个逆序列的首元素，flag是表示上一个逆序列首元素，step+1是本次逆序列首元素
Code
//#pragma warning(disable:4996) 与本文无关，是为了能在VS2017中继续使用scanf function
#include<stdio.h>
#define SIZE 1000
void inputNumber(int * array, int length);
int existSequence(int * array, int capacity, int length);
int main(void) {
int capacityOfStack;
int lengthOfPush;
int numberOfSequence;
int stack[SIZE];
int top = -1;
scanf("%d %d %d", &capacityOfStack, &lengthOfPush, &numberOfSequence);
for (int i = 0; i < numberOfSequence; i++) {
inputNumber(stack, lengthOfPush);
if (existSequence(stack, capacityOfStack, lengthOfPush)) {
printf("YES\n");
}else {
printf("NO\n");
}
}
return 0;
}
void inputNumber(int * array, int length) {
for (int i = 0; i < length; i++) {
scanf("%d", &array[i]);
}
}
int existSequence(int * array, int capacity, int length) {
int count = 0;
int flag = 0;
int step = 0;
if (capacity == 1){
for (int i = 1; i < length; i++,step++) {
if (array[step] > array[step + 1]){
return 0;
}
}
}else {
for (; step < length - 1; step++) {
if (array[step] > array[step + 1]) {
count++;
if (count > capacity-1) {
return 0;
}
}
else {
count = 0;
if (array[flag] > array[step + 1]) {
return 0;
}
flag = step + 1;
}
}
return 1;
}
}
Summary
感觉比上一道Reversing Linked List简单得多啊，只要找到可能序列的特点就很容易通过了，就是想到这个特点要花点时间，不过也不是很难。希望以后也能这么容易AC...
写这道题时，加强了对特殊边界的考虑，让我在写的时候顺畅许多，还是要养成这个习惯啊QAQ
