LeetCode——验证栈序列

秒速五厘米 2022-02-20 09:15 68阅读 0赞

题目：

给定 `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 <= pushed.length == popped.length <= 1000`
2.  `0 <= pushed[i], popped[i] < 1000`
3.  `pushed` 是 `popped` 的排列。

**思路**：输入的序列不是有序的，所以这种题就是判断循环结束后，两个数组能否都遍历完，如果都遍历完，则说明是正确的。遍历的过程就是栈顶和pop数组元素一样，则出栈，不一样，则将pushed的元素压栈

**代码**：

public boolean validateStackSequences(int[] pushed, int[] popped) {
            //栈
            Stack<Integer> stack = new Stack<>();
            //pushed索引
            int index1 = 0;
            //pop索引
            int index2 = 0;
            while(index2 < popped.length){
                if(stack.empty() || stack.peek() != popped[index2]){
                    //当push遍历完，而pop没有遍历完，则直接错误
                    if(index1 == pushed.length){
                        return false;
                    }
                    stack.push(pushed[index1 ++]);
                }else if(stack.peek() == popped[index2]){
                    stack.pop();
                    index2 ++;
                }
            }
    
    
            return true;
        }