Links

31.栈的压入、弹出序列

一、 题目

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1:
  • 输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
  • 输出:true
    解释:我们可以按以下顺序执行:
    push(1), push(2), push(3), push(4), pop() -> 4,
    push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
    示例 2:
  • 输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
  • 输出:false
    解释:1 不能在 2 之前弹出。
    提示:
    0 <= pushed.length == popped.length <= 1000
    0 <= pushed[i], popped[i] < 1000
    pushed 是 popped 的排列。
    注意:本题与主站 946 题相同:https://leetcode-cn.com/problems/validate-stack-sequences/
    来源:力扣(LeetCode)
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、 分析

本题一上来难以找到思路。对于这样的问题,举例子找规律是比较合适的。这样在面试的时候面试官也更能理解我们的思路,而不是上来直接把答案 默写 出来。
解决这个问题很直观的想法就是建立一个辅助栈,把输入的第一个序列中的元素依次压入,并按照第二个序列的顺序依次冲该栈中弹出元素。

2.1 举例分析

输入一:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

步骤
操作
弹出数字
1
压入1
1
2
压入2
12
3
压入3
123
4
压入4
1234
5
弹出4
123
4
6
压入5
1235
7
弹出5
123
5
8
弹出3
12
3
9
弹出2
1
2
10
弹出1
1

输入二:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

步骤
操作
弹出数字
1
压入1
1
2
压入2
12
3
压入3
123
4
压入4
1234
5
弹出4
123
4
6
弹出3
12
3
7
压入5
125
8
弹出5
12
5
尝试弹出下一个1,但是栈顶元素为2,无法弹出

规律总结

从这里我们发现了如下规律:
  • 栈顶元素如果等于下一个弹出元素:可以弹出
  • 栈顶元素不等于下一个弹出元素:可以压入下一个待压入的元素
    • 直到将下一个需要弹出的元素入栈
  • 如果所有元素都入栈后,没有下一个能弹出的元素,那么就不是一个弹出序列

三、 编码

func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
if pushed.isEmpty {
return true
}
var result: [Int] = [], pA = 0, pB = 0
while pB < popped.count {
let b = popped[pB]
// 栈顶元素如果等于下一个弹出元素:可以弹出
if let top = result.last, top == b {
result.removeLast()
pB += 1
}
// 栈顶元素不等于下一个弹出元素:可以压入下一个待压入的元素
else if pA < pushed.count {
let a = pushed[pA]
result.append(a)
pA += 1
}
// 如果所有元素都入栈后,没有下一个能弹出的元素,那么就不是一个弹出序列
else {
return false
}
}
return result.isEmpty
}
LeetCode

四、 本题考点

  • 考察分析复杂问题的能力。刚听到这个题的时候很多人可能都没有思路。这时候可以通过举一两个例子,一步步分析压栈、弹出的过程,进而寻找规律
  • 考察对栈的理解