栈的压入、弹出序列

题目描述

示例

代码

代码1 使用栈来辅助

/*
新建一个栈，
将数组A压入栈中，
当栈顶元素等于数组B时，就将其出栈，
当循环结束时，判断栈是否为空，若为空则返回true.
*/
function IsPopOrder(pushV, popV)
{
    if(pushV.length === 0 || popV.length ===0 || pushV.length !== popV.length) return false
    
    let stack = []
    
    let j = 0
    
    for(let i = 0; i < pushV.length; i++){
        stack.push(pushV[i])
        
        /*
            结束while的两个条件
            1. 栈都弹出了
            2. 栈顶的元素 与 popV 的元素不相等
        */
        while(stack.length > 0 && stack[stack.length - 1] === popV[j]){
            stack.pop()
            j++
        }
    }
    return stack.length === 0
}

时间复杂度O(n)

空间复杂度O(n)：用了一个栈，最坏情况全部入栈

题目来源

JZ31 栈的压入、弹出序列