剑指Offer-面试题31-栈的压入、弹出序列

2020-05-01

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列{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:

1
2
3

输入：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的排列

思路

遍历pushed，逐个压入栈，压栈过程中，根据栈顶元素与popped中的元素进行比较来模拟popped的出栈，如果最后栈中元素全都可以出栈（栈为空），即说明可以按照popped序列弹出。

代码

class Solution{
    public boolean validateStackSequences(int[] pushed,int[] popped){
        Stack<Integer> stack = new Stack<>();   //创建一个栈进行模拟
        int index = 0;  //popped数组的索引
        int len = pushed.length;    //数组长度
        for(int i=0;i<len;i++){ //遍历数组
            stack.push(pushed[i]);  //压栈
            //若栈不为空、popped遍历完且与栈顶相等，则出栈，index后移
            while(!stack.isEmpty() && index<len && stack.peek()==popped[index]){
                stack.pop();
                index++;
            }
        }
        //遍历完pushed数组后，若能把栈中元素全部弹出，说明能按照popped数组的序列出栈
        return stack.isEmpty();
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。