前往
大廳
主題

LeetCode - 946. Validate Stack Sequences 解題心得

Not In My Back Yard | 2022-11-13 12:00:11 | 巴幣 0 | 人氣 237

題目連結:


題目意譯:
給定兩個整數陣列 pushed 和 popped,每個陣列都各自包含相異整數。如果兩者可以是在一個一開始為空的堆疊上執行某個序列的 push(放入堆疊)和 pop(移出堆疊)之操作的結果所形成的話,回傳真;反之,回傳假。

限制:
1 ≦ pushed.length ≦ 1000
0 ≦ pushed[i] ≦ 1000
pushed 中所有元素相異。
popped.length == pushed.length
popped 為 pushed 的一個排列。



範例測資:
範例 1:
輸入: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
輸出: true
解釋: 我們可以做出以下操作序列:
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 之前被移出堆疊。


解題思維:
本質上跟這題是一樣的。只是該題的 pushed 序列固定為由小到大的 1 ~ n(n 為給定的正整數),但是本題的精神是一致的——模擬看看即可。

另一個方式就是把 pushed 中的數字重新編號成 1 ~ n,然後也把 popped 中的數字改成對應的樣子。之後兩題就完全等價了。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作