出栈的合法性

33出栈合法性

时间限制：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

模拟栈

每次入栈就判断能否按照题目的序列出栈

最终栈为空，则序列合法

import java.io.OutputStream;
import java.util.*;

public class Main {
    static double a ;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int len = in.nextInt();
            if(len == 0) break;
            int[] nums = new int[len];
            for(int i = 0; i < len; i++){
                nums[i] = in.nextInt();
            }
            if(isValidPop(nums)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }

        }
    }

    public static boolean isValidPop(int[] nums){
        //模拟栈
        int j = 0;
        Stack<Integer> st = new Stack<>();
        for(int i = 1; i <= nums.length; i++){
            st.push(i);
            while (!st.isEmpty() && st.peek() == nums[j]){
                st.pop();
                j++;
            }
        }
        if(st.isEmpty()){
            return true;
        }else{
            return false;
        }
        
    }
}

对于当前元素 x，若出栈序列合法，需满足 x 之后所有小于 x 的元素为递减的。

import java.io.OutputStream;
import java.util.*;

public class Main {
    static double a ;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int len = in.nextInt();
            if(len == 0) break;
            int[] nums = new int[len];
            for(int i = 0; i < len; i++){
                nums[i] = in.nextInt();
            }
            if(isValidPop(nums)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }

        }
    }

    public static boolean isValidPop(int[] nums){
        for(int i = 0; i < nums.length; i++){
            int x = nums[i];
            for(int j = i + 1; j < nums.length; j++){
                if(nums[j] > nums[i]) continue;
                if(nums[j] > x) return false;
                x = nums[j];
            }
        }
        return true;
    }
}