[[438052]]

本文轉(zhuǎn)載自微信公眾號「程序員千羽」，作者程序員千羽 。轉(zhuǎn)載本文請聯(lián)系程序員千羽公眾號。

 Leetcode : https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof

“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_24_validateStackSequences/Solution.java

棧的壓入、彈出序列

“題目描述 ：輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如，序列 {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 
解釋：我們可以按以下順序執(zhí)行： 
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 之前彈出。 

• 提示：

0 <= pushed.length == popped.length <= 1000

0 <= pushed[i], popped[i] < 1000

pushed 是 popped 的排列。

解題思路： 用棧來壓入彈出元素，相等則出棧。

如下圖所示，給定一個壓入序列 pushed和彈出序列 popped，則壓入 / 彈出操作的順序(即排列)是 唯一確定 的。

如下圖所示，棧的數(shù)據(jù)操作具有 先入后出 的特性，因此某些彈出序列是無法實現(xiàn)的。

考慮借用一個輔助棧stack，模擬壓入1彈出操作的排列。根據(jù)是否模擬成功,即可得到結(jié)果。

• 入棧操作：按照壓棧序列的順序執(zhí)行
• 出棧操作：每次入棧后，循環(huán)判斷“棧頂元素=彈出序列的當前元素”是否成立,將符合彈出序列順序 的棧頂元素全部彈出。

由于題目規(guī)定|棧的所有數(shù)字均不相等， 因此在循環(huán)入棧中，每個元素出棧的位置的可能性是唯一的(若有重復數(shù)字，則具有多個可出棧的位置)。因而， 在遇到“棧頂元素=彈出序列的當前元素”就應立即執(zhí)行出棧。

• 算法流程:
• 初始化：輔助棧stack，彈出序列的索引i ;
  • 遍歷壓棧序列：各元素記為num ;
  • 元愫num入棧;
  • 循環(huán)出棧:若stack的棧頂元素=彈出序列元素popped[i]，則執(zhí)行出棧與i++ ;

返回值:若stack為倥,則此彈出序列合法。

復雜度分析:

• 時間復雜度O(N): 其中N為列表pushed的長度;每個元素最多入棧與出棧一次,即最多共2N次出入棧操作。
• 空間復雜度O(N): 輔助棧stack最多同時存儲N個元素。

package com.nateshao.sword_offer.topic_24_validateStackSequences; 
 
import java.util.Stack; 
 
/** 
 * @date Created by 邵桐杰 on 2021/11/28 21:53 
 * @微信公眾號 程序員千羽 
 * @個人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 棧的壓入、彈出序列 
 * 輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。 
 * 假設(shè)壓入棧的所有數(shù)字均不相等。例如，序列 {1,2,3,4,5} 是某棧的壓棧序列， 
 * 序列 {4,5,3,2,1} 是該壓棧序列對應的一個彈出序列，但 {4,3,5,1,2} 就不可能是該壓棧序列的彈出序列。 
 * https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof 
 */ 
public class Solution { 
    public static void main(String[] args) { 
        int[] pushed = {1, 2, 3, 4, 5}; 
        int[] popped = {4, 5, 3, 2, 1}; 
        int[] popped1 = {4, 3, 5, 1, 2}; 
        boolean b = validateStackSequences1(pushed, popped); 
        System.out.println("b = " + b);// b = true 
        boolean b1 = validateStackSequences2(pushed, popped1); 
        System.out.println("b1 = " + b1); 
    } 
 
    /** 
     * 精選解答 
     * 
     * @param pushed 
     * @param popped 
     * @return 
     */ 
    public static boolean validateStackSequences1(int[] pushed, int[] popped) { 
        if (pushed == null || pushed == null) return false; 
        Stack<Integer> stack = new Stack<>(); 
        int index = 0; 
        for (int num : pushed) { 
            stack.push(num); 
            while (!stack.isEmpty() && stack.peek() == popped[index]) { 
                stack.pop(); 
                index++; 
            } 
        } 
        return stack.isEmpty(); 
    } 
 
    /** 
     * 思路：用棧來壓入彈出元素，相等則出棧。 
     * 
     * @param pushed 
     * @param popped 
     * @return 
     */ 
    public static boolean validateStackSequences2(int[] pushed, int[] popped) { 
        if (pushed == null || popped == null) return false; 
        Stack<Integer> stack = new Stack<>();// 借用一個輔助棧stack 
        int index = 0; 
        for (int i = 0; i < pushed.length; i++) { 
            stack.push(pushed[i]);// 入棧 
            //循環(huán)判斷 棧不為空 && 棧頂元素 == 彈出序列的當前元素 
            while (!stack.isEmpty() && stack.peek().equals(popped[index])) { 
                stack.pop(); 
                index++; 
            } 
        } 
        return stack.isEmpty(); 
//        return index==popped.length; 
    } 
} 

參考鏈接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solution/mian-shi-ti-31-zhan-de-ya-ru-dan-chu-xu-lie-mo-n-2