017.出栈合法性

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

答案 §

package main
 
import (
    "bufio"
    "os"
    "fmt"
    "strings"
    "strconv"
)
 
var (
    n int
    arr []int
    stack []int
    idx int
)
 
func main() {
    input := bufio.NewScanner(os.Stdin)
    for input.Scan() {
        n, _ := strconv.Atoi(input.Text())
        if n == 0 {
            break
        }
        input.Scan()
        arr = make([]int, n)
        for i, str := range strings.Fields(input.Text())[:n] {
            num, _ := strconv.Atoi(str)
            arr[i] = num
        }
        stack = make([]int, 0, n)
        idx = 0
        for i := range arr {
            stack = append(stack, i + 1)
            for len(stack) > 0 && stack[len(stack) - 1] == arr[idx] {
                stack = stack[:len(stack) - 1]
                idx++
            }
        }
        if len(stack) == 0 && idx == n {
            fmt.Println("Yes")
        } else {
            fmt.Println("No")
        }
    }
}