剑指offer—验证栈序列 解答

剑指offer—验证栈序列

题目描述

给定 pushed 和 popped 两个序列,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。

示例 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 之前弹出。

思路

我们可以使用辅助栈实现,循环入栈元素,如果当前栈顶元素与验证序列对应位置的数相等,则执行出栈,并且让位置标号+1,循环进行(有可能出栈一个元素后栈顶元素还需要出栈),当结束入栈后,最后返回栈是否为空,为空说明这是一个正确的序列。

  • 位置标号:从0开始,每出栈一个元素,位置标号+1,它指向验证序列第一个未出栈的元素
  1. 定义一个辅助栈;
  2. 遍历pushed数组,先将当前数字放入栈中,判断栈顶元素是否为popped数组的第一个数字,如果是就pop,并且index指针移动到poped数组的下一个位置,继续循环判断;
  3. 最后判断stack中的元素是否全部被pop完即可,即判断栈空;

代码

class Solution {
    public boolean validateStackSequences(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        int flag = 0;
        for(int i=0;i<pushA.length;i++){
            stack.push(pushA[i]);
            while(!stack.isEmpty()&&popA[flag]==stack.peek()){
                stack.pop();
                flag++;
            }
        }
        return stack.isEmpty();
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/stack-sequence.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!