面试题31. 栈的压入、弹出序列

栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例：

输入：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

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

转载来源：力扣（LeetCode）

题目分析

思路：

1. 创建一个栈（直接用栈也好用数组模拟栈也罢）
2. pushed里的元素逐个进栈
3. 每进一个都和poped的头元素对比
   3.1 如果相同，栈pop，poped数组就像一个队列一样，将头元素poll，然后继续对比栈的peek和队列的peek
   3.2 两者不等，回到2，继续执行

import java.util.*
class Solution {
    fun validateStackSequences(pushed: IntArray, popped: IntArray): Boolean {
        if(pushed.isEmpty()) return true
        val stack = Stack<Int>()
        var popIndex = 0
        for(i in 0 until pushed.size){
            stack.push(pushed[i])
            while(stack.isNotEmpty()){
                if(stack.peek() == popped[popIndex]){
                    popIndex++
                    stack.pop()
                }else{
                    break
                }
            }
        }
        return stack.isEmpty()
    }
}