<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
TypeScript棧的壓入與彈出序列校驗
2022-09-16 22:03:45
前言
有兩個整數序列，第一個序列表示棧的壓入順序，判斷第二個序列是否為該棧的彈出順序。假設壓入棧的數位均不相等。例如，序列[1, 2, 3, 4, 5]是某棧的壓棧序列，序列[4, 5, 3, 2, 1]是該棧序列對應的一個彈出序列，但[4, 3, 5, 1, 2]就不可能是該壓棧序列的彈出序列。
思路分析
仔細分析題目後，我們很直觀的想法就是構造一個輔助棧，把壓入序列中的數位依次壓入該輔助棧。按照彈出序列的順序依次從該棧中彈出數位，如果輔助棧被清空則代表此序列是它的一個彈出序列，否則就不可能是一個彈出序列。
彈出序列滿足條件
如下圖所示，它的壓入過程為：
取出彈出序列的第1個元素，維護一個已取索引，在壓入序列中從已取索引位置開始尋找與之相等的元素，將它之前的數位和其本身依次入棧，每取1個元素就將索引自增1次
- 此時，棧頂元素與彈出序列的第1個元素相等，將棧頂元素出棧。
取出彈出序列的第2個元素，在壓入序列中從已取索引位置開始尋找與之相等的元素，將它之前的數位和其本身依次入棧。
- 此時，棧頂元素與彈出序列的第2個元素相等，將棧頂元素出棧。
取出彈出序列的第3個元素，此時，壓入序列的元素已經被取完。我們繼續判斷 輔助棧中的元素是否與彈出序列的元素相等。
- 棧頂元素為3，要彈出的元素也是3，二者相等，棧頂元素出棧
取出彈出序列的第4個元素
- 棧頂元素為2，要彈出的元素也是2，二者相等，棧頂元素出棧
取出彈出序列的第5個元素
- 棧頂元素為1，要彈出的元素也是1，二者相等，棧頂元素出棧
彈出序列已取完，輔助棧已清空。 該彈出序列屬於壓入序列的一個彈出順序
彈出序列不滿足條件
接下來，我們來分析下它不是壓入序列的彈出順序的情況，它的壓入過程與滿足條件時一樣，唯獨不同的是，彈出序列的第3個元素從輔助棧出棧後，壓入序列已經被取完。此時，彈出序列的第4個元素是1，輔助棧的棧頂元素是2，二者不等，那麼該序列肯定不是壓入序列的彈出順序。
實現程式碼
經過上面的分析，我們已經知道了如何解決這個問題。思路已明確，接下來，我們就可以愉快的進入編碼環節了
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45