栈的可生成性

给定一个 int 数组（元素位于 [0,N-1]，且元素不重复)，判断该数组是否可以由 0,1,…,N-1 依次入栈出栈得到，例如 2 1 4 3 6 5 8 7 9 0 可以由入栈出栈得到：

思路：使用 index 表示当前操作到的数字。依次遍历数组，如果当前元素值 element 大于 index，则将[index，element) 依次添加到栈中；如果 element = index，则进行下一次遍历；如果 element<index，则弹出栈顶数据 d，并比较 d 与 element 的关系，只要不相等就返回 false，否则进行下一次循环：

fun isValid(str: Array<Int>): Boolean {
    val stack = Stack<Int>()
    var index = 0
    for (i in str) {
       // 添加 [index,element) 到栈中
        while (index < i) {
            stack.add(index++)
        }
        // 弹出栈顶元素进行比较
        if (index > i) {
            if (stack.pop() != i) return false
        }
        // 跳过当前元素
        if (index == i) index++
    }
    return true
}

1.3.46

参考

一个合法的出栈顺序编号当且仅当对任意的 pm (m >= 1 且 m < n)，从 pm+1开始，所有小于 pm 的子串严格单调递减。