題目連結:
題目意譯:
給定兩個整數陣列 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 中的數字改成對應的樣子。之後兩題就完全等價了。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。