题目

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

题目大意

大意就是 给从1到N的长度数据，然后用一个M大小的栈来存放，判断是否可以输出sample中所给的顺序
注意：这里的栈刚刚开始只放小于M的任意数量，其余的数可以选择放入或者暂时不放入
；例如 测试用例中所给的 1 2 3 4 5 6 7 就可以刚刚开始只给栈中放1个数据（1<5)然后取出来，接着放2，以此类推。 5 6 4 3 7 2 1： 1 2 3 4 5压入栈中，先Pop5 输出，再Push 6 ，接着Pop 6 再Pop 4 3 再Push 7 再Pop 2 1


#include < stdio.h>
#include < stdlib.h>
#define MAXSIZE 1001
#define LEN ((MAXSIZE + 1) * sizeof(int))
typedef struct QStack* Stack;
struct QStack
{
    int Data[MAXSIZE];
    int top;//栈顶“指针”
};
int main()
{
    int N, M, K;
    int arry[MAXSIZE];//用来存放遍历元素
    scanf("%d%d%d", &M, &N, &K); //M Stack最大，N 长度，K 行数
    while (K--)
    {
        int x=1, temp = 1;
        Stack p = (Stack)malloc(LEN);
        p->top = 1;
        p->Data[p->top] = 1;//先只在栈中放一个元素
        for (int x = 1; x <= N; x++)
            scanf("%d", &arry[x]);
        while(x<=N)
        {
            if (p->top > M || arry[x] < p->Data[p->top])
                // 如果栈溢出 或者 遍历的元素比栈顶元素还小 就break
                break;
            if (arry[x] == p->Data[p->top])
            {
                p->top--;
                x++;
            }
            else
                p->Data[++p->top] = ++temp;//如果没有找到就往栈中再加元素
        }
        if (x == N + 1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

思路

我们所能操作的数（与遍历元素比较的数）只有栈顶元素与遍历元素，关键就是观察出栈顶元素与遍历元素，观察出所遍历的元素必定是等于栈顶元素或者是未入栈的元素，由于递增数列这时便有栈顶元素必定小于未入栈元素，–>所遍历的元素大小必须是大于或者等于栈顶元素

总结

1.分析题目中所能操作的数（关键数）这题中便是栈顶
2.可以借鉴x==N+1来取代flag 判断是否每次循环都是“真”

Time

2020 4 15 22：33

今天这题花了好久时间才弄清题目，今天有点梦游，加油！！！
路漫漫其修远兮，吾将上下而求索。