17. 出栈合法性

时间限制：1.000S 空间限制：32MB

题目描述

已知自然数1，2，...，N（1<=N<=100）依次入栈，请问序列C1，C2，...，CN是否为合法的出栈序列。

输入描述

输入包含多组测试数据。 每组测试数据的第一行为整数N（1<=N<=100），当N=0时，输入结束。 第二行为N个正整数，以空格隔开，为出栈序列。

输出描述

对于每组输入，输出结果为一行字符串。 如给出的序列是合法的出栈序列，则输出Yes，否则输出No。

输入示例

5

3 4 2 1 5

5

3 5 1 4 2

0

输出示例

Yes

No

解法一(模拟)

思路分析:

1. 模拟判断出栈队列是否合理
2. 维护两个变量记录下一次可能出栈的值,若不符合,则肯定不合法

实现代码如下:

public class k_17_PoppingLegality {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n;
        while (in.hasNext() && (n = in.nextInt()) != 0) {
            int[] nums = new int[n+1];
            for (int i = 0; i < n; ++ i) {
                nums[i] = in.nextInt();
            }
            System.out.println(judgeLegality(n, nums));
        }
    }
    private static String judgeLegality(int n, int[] nums) {
        // 记录下一个出栈的 小数
        int left = nums[0]-1;
        // 记录下一个出栈的 大数
        int right = nums[0] + 1;
        for (int i = 1; i < n; ++ i) {
            if (left < 0) {
                return "No";
            }
            if (nums[i] == left || nums[i] == right) {
                // 为其一的合法输入
                if (nums[i] == right) {
                    // 出栈为 大数 则更新下次所可能出栈的数
                    right = nums[i] + 1;
                } else if (nums[i] == left) {
                    left = nums[i] - 1;
                }
            } else {
                return "No";
            }
        }
        return "Yes";
    }
}

运行结果如下:

运行时间： 464ms 消耗内存： 15700kb

复杂度分析:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$