※ 引述《pandix (面包屌)》之铭言
: 946. Validate Stack Sequences
: 给你两个 array pushed 和 popped
: 问你有没有办法照顺序 push 进 stack 且以 popped 的顺序出来
: Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
: Output: true
: push(1), stack = [1]
: push(2), stack = [1, 2]
: push(3), stack = [1, 2, 3]
: push(4), stack = [1, 2, 3, 4]
: pop() -> 4, stack = [1, 2, 3]
: push(5), stack = [1, 2, 3, 5]
: pop() -> 5, stack = [1, 2, 3]
: pop() -> 3, stack = [1, 2]
: pop() -> 2, stack = [1]
: pop() -> 1, stack = []
: Example 2:
: Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
: Output: false
: push(1, 2, 3, 4), stack = [1, 2, 3, 4]
: pop() -> 4, stack = [1, 2, 3]
: pop() -> 3, stack = [1, 2]
: push(5), stack = [1, 2, 5]
: pop() -> 5, stack = [1, 2]
: 没办法pop 1, 失败
: 思路:
: 1.就是模拟 stack,多维护一个 popped 的 index 代表当前要 pop 的目标
: 如果目前 stack 的顶部等于目标就执行 pop
: 最后看目标有没有走完 popped 或是看 stack 里有没有东西
不好意思好奇问一下
如果题目改成可以有重复的数字还能用同样的方法做吗
我找不到反例但也证不出是对的