LeetCode_Stack_946. Validate Stack Sequences 驗證棧序列（Java）【棧，模拟】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​三，AC代碼​​

​​Java​​

​​四，解題過程​​

​​第一博​​

一，題目描述

英文描述

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

中文描述

給定 pushed 和 popped 兩個序列，每個序列中的 值都不重複，隻有當它們可能是在最初空棧上進行的推入 push 和彈出 pop 操作序列的結果時，傳回 true；否則，傳回 false 。

示例與說明

示例 1：

示例 2：

提示：

來源：力扣（LeetCode）

連結：​​​https://leetcode-cn.com/problems/validate-stack-sequences​​ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

用兩個指針i、j分别指向pushed、popped。

以i指針為基準周遊pushed序列。每次循環先将pushed[i]壓入堆棧，然後根據棧頂和popped序列中的值是否相等來判斷是否彈棧以及j指針遞增。

三，AC代碼

Java

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> record = new Stack<>();
        for (int i = 0, j = 0; i < pushed.length; i++) {
            record.push(pushed[i]);
            while (!record.isEmpty() && record.peek() == popped[j]) {
                record.pop();
                j++;
            }
        }
        return record.isEmpty();
    }
}      

四，解題過程

第一博