補(bǔ)充：10.10，今天想到這個(gè)算法空間復(fù)雜度其實(shí)可以更小的，甚至不需要數(shù)組來存儲(chǔ)，我們直接使用在線處理的思想就好，用變量記下逆序列的第一個(gè)元素，在逆序列輸出結(jié)束時(shí)，比較第一個(gè)元素和新輸入的元素即可

問題描述

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：序列的元素?cái)?shù)量
K：需要判斷序列的數(shù)量
M,N,K<=1000
給你一個(gè)序列
讓你判斷所給序列是否可能是以1 2.....N的順序壓棧，然后隨意時(shí)間，隨意出棧元素個(gè)數(shù)所形成的序列
第一行表示：
[M N K]
2-K行
需要判斷的序列

解決思路

通過仔細(xì)觀察，可以得出：
所有可能的序列都有以下的特征：
1.序列最多具有N個(gè)逆序列（逆序列元素只有一個(gè)也算在其中）
2.下一個(gè)逆序列首元素大于上一個(gè)逆序列首元素（第一個(gè)不計(jì)入其中）
3.每個(gè)逆序列元素個(gè)數(shù)不能大于棧的容量M

逆序列：元素從小到大的序列

著重講解2.3點(diǎn)
第二點(diǎn)：因?yàn)槭前磸男〉酱蟮捻樞驂簵?，所以每次出棧的元素都?huì)形成一個(gè)逆序列Q，而下一次形成逆序列K時(shí)，逆序列k的首元素都會(huì)大于逆序列Q的首元素
仔細(xì)想想，這是由于從小到大的壓棧所形成特性！

第三點(diǎn)：因?yàn)闂５娜萘繘Q定了逆序列元素的數(shù)量

Some Detail Of Function（含有寫題時(shí)的思路，感想，建議結(jié)合代碼閱讀

existSequence：判斷序列是否是可能的出棧序列
當(dāng)M == 1，只能是原樣輸出，所以只需要遍歷查看是否是1 2 3.....N
當(dāng)M != 1，只要判斷有不符合三個(gè)特征之一，便可以return false。
遍歷比較array[step]和array[step+1]的大小，如果step > step+1 判斷count是否>M+1(這里懶得寫array，下同）

在這里，使用count來表示逆序列的元素?cái)?shù)量，由于step 和 step + 1比較，所以count不能大于M-1（第三點(diǎn)）
如果小于，比較兩個(gè)逆序列的首元素，flag是表示上一個(gè)逆序列首元素，step+1是本次逆序列首元素

image.png

Code

//#pragma warning(disable:4996) 與本文無關(guān)，是為了能在VS2017中繼續(xù)使用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簡單得多啊，只要找到可能序列的特點(diǎn)就很容易通過了，就是想到這個(gè)特點(diǎn)要花點(diǎn)時(shí)間，不過也不是很難。希望以后也能這么容易AC...

寫這道題時(shí)，加強(qiáng)了對特殊邊界的考慮，讓我在寫的時(shí)候順暢許多，還是要養(yǎng)成這個(gè)習(xí)慣啊QAQ