题目地址(31. 栈的压入、弹出序列)

https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

题目描述

  1. 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
  5. 示例 1：
  7. 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
  8. 输出：true
  9. 解释：我们可以按以下顺序执行：
  10. push(1), push(2), push(3), push(4), pop() -> 4,
  11. push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
  14. 示例 2：
  16. 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
  17. 输出：false
  18. 解释：1 不能在 2 之前弹出。
  23. 提示：
  25. 0 <= pushed.length == popped.length <= 1000
  26. 0 <= pushed[i], popped[i] < 1000
  27. pushed 是 popped 的排列。
  29. 注意：本题与主站 946 题相同：https://leetcode-cn.com/problems/validate-stack-sequences/

前置知识


公司

  • 暂无

思路

使用一个辅助栈 按照入栈顺序 把数据压入栈 如果碰到和栈顶一样的数据 就将栈弹出 然后依次往后遍历 如果顺序没错 栈最后会为空

关键点


代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.     public boolean validateStackSequences(int[] pushed, int[] popped) {
  3.         Stack<Integer> stack = new Stack<>();
  4.         //push的下标
  5.         int i = 0;
  6.         //pop的下标
  7.         int j = 0;
  8.         //遍历一遍push
  9.         while (i < pushed.length) {
  10.             //把pushed 压入栈
  11.             stack.push(pushed[i]);
  12.             //压入栈后判断栈顶是否和popped数组的第一个数相等 相等就pop 然后继续判断直到不相等
  13.             while (!stack.isEmpty() && stack.peek() == popped[j]) {
  14.                 stack.pop();
  15.                 j++;
  16.             }
  17.             //让push下标往前走
  18.             i++;
  19.         }
  20.         //最后如果栈是空的 说明顺序没错
  21.         return stack.isEmpty();
  22.     }
  23. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 31. 栈的压入、弹出序列 - 图1#card=math&code=O%28n%29&id=IeN3V)
  • 空间复杂度：剑指 Offer 31. 栈的压入、弹出序列 - 图2#card=math&code=O%28n%29&id=ZtUhl)