每天一道劍指offer-棧的壓入、彈出序列

• 2019 年 10 月 4 日
• 筆記

前言

今天的題目 每天的題目見github(看最新的日期): https://github.com/gzc426 具體的題目可以去牛客網對應專題去找。

昨天的題解

題目

每天一道劍指offer-棧的壓入、彈出序列 來源：牛客網對應專題

題目詳述

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

題目詳解

思路

• 一個彈出序列，一個壓棧序列，彈出序列中的數，比如第一個彈出的數，肯定是在壓棧過程中彈出來的，所以在這裡新建一個棧stack,如果壓棧序列中要壓入的數和彈出序列當前的數不一樣（說明沒找到），那麼壓棧序列繼續壓，直到壓棧序列中找到了和彈出序列當前下標值相等的數，那麼彈出序列的下標值就+1,。
• 結束條件就是彈出序列的下標值可以到達序列的末尾。

程式碼

import java.util.*;  public class Solution {      public boolean IsPopOrder(int [] pushA,int [] popA) {          if(pushA.length != popA.length)              return false;          Stack<Integer> stack1 = new Stack<>();//棧記錄壓棧          int j = 1;          stack1.push(pushA[0]);//棧中先壓入push壓棧序列的第一個數          for(int i=0;i<popA.length;i++)          {              while(j < pushA.length && stack1.peek() != popA[i])              {//如果棧頂的數和彈出序列不一樣，就一直壓棧，因為必須是從棧頂彈出的！                  stack1.push(pushA[j]);                  j++;              }              if(j >= pushA.length && stack1.peek() != popA[i])                  return false;//如果j已經到達壓棧序列的末尾，但是棧頂的數還是和彈出序列當前的數不一致                               //說明沒有這個序列              stack1.pop();          }          return true;      }  }