17. 出栈合法性

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int main() {
    int n;
    int nums[105];
    while(cin >> n) {
        if (n == 0) break;
        for (int index = 0; index < n; index++) cin >> nums[index]; // 输入数组
        stack<int> st;
        int index = 0;
        for (int i = 1; i <= n; i++) { // 判断出栈合法性
            st.push(i);
            while (!st.empty() && st.top() == nums[index]) {
                st.pop();
                index++;
            }
        }
        if (st.empty() && index == n) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        while((str = reader.readLine())!= null){
            StringTokenizer tokenizer = new StringTokenizer(str);
            int n = Integer.parseInt(tokenizer.nextToken());
            if(n == 0){
                break;
            }
            int[] arr = new int[n];
            tokenizer = new StringTokenizer(reader.readLine());
            for(int i = 0; i < n; i++){
                arr[i] = Integer.parseInt(tokenizer.nextToken());
            }
            if(check(arr)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
    }
    public static boolean check(int[] arr){
        int n = arr.length;
        int[] st = new int[n];
        int top = -1;
        int k = 1;
        for(int i = 0; i < n; i++){
            while(top == -1 || st[top] < arr[i]){
                st[++top] = k++;
            }
            if(st[top] != arr[i]){
                return false;
            }
            top--;
        }
        return true;
    }
}

// 方法二：使用栈模拟
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            int n = sc.nextInt();
            if (n == 0)
                break;

            int[] poppedSequence = new int[n];
            for (int i = 0; i < n; i++)
                poppedSequence[i] = sc.nextInt();

            if (isValidPopSequence(n, poppedSequence))
                System.out.println("Yes");
            else
                System.out.println("No");
        }
        sc.close();

    }

    private static boolean isValidPopSequence(int n, int[] poppedSequence) {
        Stack<Integer> stack = new Stack<>();
        int expected = 1; // 期望的下一个弹出元素
        int i = 0; // 指针用于遍历弹出序列数组

        while (i < n) {
            if (!stack.isEmpty() && stack.peek() == poppedSequence[i]) {
                // 如果栈顶元素与当前弹出元素匹配，则从栈中弹出并移动到下一个弹出元素
                stack.pop();
                i++;
            } else if (expected <= n) {
                // 如果栈顶元素与当前弹出元素不匹配，并且还有元素可以推入栈中，则推入下一个元素到栈中，并更新期望的元素值
                stack.push(expected);
                expected++;
            } else {
                // 如果栈顶元素与当前弹出元素不匹配，并且没有元素可以再推入栈中，则弹出序列无效
                return false;
            }
        }

        return true;
    }
}

while True:
    n = int(input())
    if n == 0:
        break
    sequence = list(map(int, input().split()))
    stack = []
    current = 1
    possible = True
    for num in sequence:
        while current <= num:
            stack.append(current)
            current += 1
        if stack[-1] == num:
            stack.pop()
        else:
            possible = False
            break
    if possible:
        print('Yes')
    else:
        print('No') 

package main

import (
	"fmt"
)

func main() {
	for {
		var n int
		_, _ = fmt.Scan(&n)

		if n == 0 {
			break
		}

		nums := make([]int, n)
		for i := 0; i < n; i++ {
			_, _ = fmt.Scan(&nums[i])
		}

		stack := make([]int, 0)
		index := 0

		for i := 1; i <= n; i++ {
			stack = append(stack, i)
			for len(stack) > 0 && stack[len(stack)-1] == nums[index] {
				stack = stack[:len(stack)-1]
				index++
			}
		}

		if len(stack) == 0 && index == n {
			fmt.Println("Yes")
		} else {
			fmt.Println("No")
		}
	}
}

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

// 因为只能一行一行地读取数据，所以用-1来表示是否是一组新的数据
let n = -1
rl.on('line', (input) => {
    line = input.split(' ').map(Number)
    if (line.length === 1 && n === -1) {
        // 如果是一组新的数据，先读入n，直接return等待下一次输入出栈序列
        n = line[0]
        return
    }
    // line保存的是出栈序列
    if (islegal(line, n)) {
        console.log('Yes')
    } else {
        console.log('No')
    }
    // 处理完一组数据后，写回n = -1
    n = -1
})

function islegal(arr, n) {
    let index = 0
    const stack = []
    // 从 1 到 n 逐个入栈
    for(let i = 1; i <= n; i++) {
        stack.push(i)
        // 如果栈不为空且栈顶元素与期望出栈元素相同，则循环执行出栈操作
        while(stack.length !== 0 && stack[stack.length - 1] === arr[index]) {
            stack.pop()
            index++
        }
    }
    // 如果 index 扫描到了数组末尾且栈为空，说明出栈序列合法
    return stack.length === 0 && index === n
}

#include <stdio.h>
#include <stdbool.h>

int main() {
    int n;
    int nums[105];
    while (scanf("%d", &n) == 1) {
        if (n == 0) break;

        for (int index = 0; index < n; index++)
            scanf("%d", &nums[index]); // 输入数组

        int index = 0;
        int i = 1;
        int st[105];
        int top = -1;

        while (i <= n) { // 判断出栈合法性
            st[++top] = i;
            while (top >= 0 && st[top] == nums[index]) {
                top--;
                index++;
            }
            i++;
        }

        if (top == -1 && index == n)
            printf("Yes\n");
        else
            printf("No\n");
    }

    return 0;
}