用stack 模擬陣列生成 Build Array w/ Stack Operations_Leetcode 1441

這題的題目在這裡:

題目敘述

題目會給我們一個陣列target，問我們從整數串流中1~n之中，如何透過stack 的 push和pop來模擬生成target指定的形式?

測試範例

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Pop the integer on the top of the stack. s = [1].
Read 3 from the stream and push it to the stack. s = [1,3].

Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Read 3 from the stream and push it to the stack. s = [1,2,3].

Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Since the stack (from the bottom to the top) is equal to target, we stop the stack operations.
The answers that read integer 3 from the stream are not accepted.

約束條件

Constraints:

• 1 <= target.length <= 100
• 1 <= n <= 100
• 1 <= target[i] <= n
• target is strictly increasing.

演算法

建造一個迴圈，每次迭代讀入一個整數，並且push到stack頂端。

假如這次迭代當下的整數是需要的，就留下來，並且更新target index。

假如這次迭代當下的整數是不需要的，就pop出去，進行下一次迭代。

最後，當target index已經走到最後一個位置，到表已經模擬生成出整個target陣列。

中間stack操作所記錄的"Push", "Pop"字串就是最終答案。

程式碼

class Solution:
　def buildArray(self, target: List[int], n: int) -> List[str]:
　　
　　target_idx, cur_read_num = 0, 1
　　
　　stack_operation = []
　　
　　while target_idx < len(target):
　　　
　　　# Push current read number
　　　stack_operation.append('Push')
　　　
　　　if target[target_idx] == cur_read_num:
　　　　# Current read number is what we need, keep it and update target index
　　　　target_idx += 1
　　　
　　　else:
　　　　# Pop out unnecessary element
　　　　stack_operation.append('Pop')
　　　　
　　　# current read number always +1 after each iteration
　　　cur_read_num += 1
　　　
　　return stack_operation

複雜度分析

時間複雜度: O( n)
從整數流中模擬target array建造，最長迭代次數和n一樣長。

空間複雜度: O(n)
從整數流中模擬target array建造，target array最長和n的大小一樣長。

關鍵知識點

熟悉stack push 和 pop的操作，結合1~n的整數流，進行陣列生成模擬。

Reference:

[1] Python O(t) sol by simulation [w/ Comment] - Build an Array With Stack Operations - LeetCode