聊聊棧的壓入、彈出序列
本文轉(zhuǎn)載自微信公眾號(hào)「程序員千羽」，作者程序員千羽 。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員千羽公眾號(hào)。
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
棧的壓入、彈出序列
“題目描述 ：輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如，序列 {1,2,3,4,5} 是某棧的壓棧序列，序列 {4,5,3,2,1} 是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但 {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 的排列。
解題思路： 用棧來(lái)壓入彈出元素，相等則出棧。
如下圖所示，給定一個(gè)壓入序列 pushed和彈出序列 popped，則壓入 / 彈出操作的順序(即排列)是 唯一確定 的。
如下圖所示，棧的數(shù)據(jù)操作具有 先入后出 的特性，因此某些彈出序列是無(wú)法實(shí)現(xiàn)的。
考慮借用一個(gè)輔助棧stack，模擬壓入1彈出操作的排列。根據(jù)是否模擬成功,即可得到結(jié)果。
- 入棧操作：按照壓棧序列的順序執(zhí)行
- 出棧操作：每次入棧后，循環(huán)判斷“棧頂元素=彈出序列的當(dāng)前元素”是否成立,將符合彈出序列順序 的棧頂元素全部彈出。
由于題目規(guī)定|棧的所有數(shù)字均不相等， 因此在循環(huán)入棧中，每個(gè)元素出棧的位置的可能性是唯一的(若有重復(fù)數(shù)字，則具有多個(gè)可出棧的位置)。因而， 在遇到“棧頂元素=彈出序列的當(dāng)前元素”就應(yīng)立即執(zhí)行出棧。
- 算法流程:
- 初始化：輔助棧stack，彈出序列的索引i ;
- 遍歷壓棧序列：各元素記為num ;
- 元愫num入棧;
- 循環(huán)出棧:若stack的棧頂元素=彈出序列元素popped[i]，則執(zhí)行出棧與i++ ;
返回值:若stack為倥,則此彈出序列合法。
復(fù)雜度分析:
- 時(shí)間復(fù)雜度O(N): 其中N為列表pushed的長(zhǎng)度;每個(gè)元素最多入棧與出棧一次,即最多共2N次出入棧操作。
- 空間復(fù)雜度O(N): 輔助棧stack最多同時(shí)存儲(chǔ)N個(gè)元素。
- package com.nateshao.sword_offer.topic_24_validateStackSequences;
- import java.util.Stack;
- /**
- * @date Created by 邵桐杰 on 2021/11/28 21:53
- * @微信公眾號(hào) 程序員千羽
- * @個(gè)人網(wǎng)站 www.nateshao.cn
- * @博客 https://nateshao.gitee.io
- * @GitHub https://github.com/nateshao
- * @Gitee https://gitee.com/nateshao
- * Description: 棧的壓入、彈出序列
- * 輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序。
- * 假設(shè)壓入棧的所有數(shù)字均不相等。例如，序列 {1,2,3,4,5} 是某棧的壓棧序列，
- * 序列 {4,5,3,2,1} 是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但 {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();
- }
- /**
- * 思路：用棧來(lái)壓入彈出元素，相等則出棧。
- *
- * @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<>();// 借用一個(gè)輔助棧stack
- int index = 0;
- for (int i = 0; i < pushed.length; i++) {
- stack.push(pushed[i]);// 入棧
- //循環(huán)判斷 棧不為空 && 棧頂元素 == 彈出序列的當(dāng)前元素
- 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
