1441. Build an Array With Stack Operations

📘 題目敘述

給你一個整數陣列 target 和一個整數 n。

你有一個空 stack，並且可以做以下兩種操作：

"Push"：把一個整數推到 stack 頂端
"Pop"：移除 stack 頂端的整數

你另外還有一個從 1 到 n 的整數串流。

請使用這兩種 stack 操作，讓 stack 中的元素（從底到頂）剛好等於 target。
你必須遵守以下規則：

如果整數串流還沒用完，就要讀取下一個整數，並把它 push 到 stack 頂端
如果 stack 不為空，就可以把 stack 頂端元素 pop 掉
如果在某個時刻，stack 中的元素（從底到頂）已經等於 target，就要立刻停止，不能再繼續讀新的整數，也不能再做更多操作

請回傳建出 target 所需要的操作序列。
如果有多種合法答案，回傳任意一種即可。

條件限制

1 <= target.length <= 100
1 <= n <= 100
1 <= target[i] <= n
target 是嚴格遞增的

🧠 解題思路

這題的重點是：

串流的數字只能照 1, 2, 3, ... 這樣一路讀下去，不能跳。
所以如果目前應該要讀到的數字不是 target 裡想要的那個，我也還是得先把它讀進來，再立刻把它丟掉。

我這份寫法是用一個 now 代表：

目前串流下一個要讀的數字是誰。

一開始 now = 1。

接著我依序處理 target 裡的每個數字 i。

如果目前 now < i，代表：

now 這個數字不是我要留下來的
但我不能跳過它
所以只能做：

"Push"
"Pop"

然後 now++，繼續看下一個串流數字。

當 now 終於等於 i 的時候，代表這個數字就是 target 需要的，那就只做一次 "Push"，把它留下來，再讓 now++。

因為 target 是嚴格遞增的，所以這樣照順序一路處理就可以，不需要回頭，也不會有歧義。

也就是說，這題的核心就是：

用 now 模擬串流目前讀到哪個數字，遇到不需要的數字就 "Push" 再 "Pop"，遇到 target 需要的數字就只 "Push" 留下來。

所有變數

now：目前串流下一個要讀的數字
ans：最後要回傳的操作序列

🪜 主要流程步驟

1. 先用 now 記錄目前串流要讀到哪個數字

int now = 1;
vector<string> ans;

這裡：

now = 1 表示串流一開始會先讀到 1
ans 用來記錄最後所有操作

之後整個過程都只是模擬：

串流現在走到哪個數字
這個數字要留下還是要丟掉

2. 依序處理 target 裡每個要留下來的數字

for (int i : target) {

這裡的 i 代表：

現在 target 希望下一個留下來的數字是 i

因為 target 本身是嚴格遞增的，所以我可以照順序一路做，不用擔心前後衝突。

3. 如果 now 還比 i 小，代表這些數字都不是我要的，要先 Push 再 Pop

while (now < i) {
    ans.push_back("Push");
    ans.push_back("Pop");
    now++;
}

這一步是整題最核心的地方。

如果現在我要的數字是 i，但串流還在 now，而且 now < i，那表示：

now 這個數字不是 target 要保留的
但題目規定串流不能跳讀
所以一定得先把它讀進 stack

既然它不是我要保留的，唯一能做的就是：

"Push"：先把它放進 stack
"Pop"：立刻把它移掉

這樣就等於「讀過了，但不留下」。

做完後 now++，表示串流往下一個數字前進。

4. 當 now 等於 i 時，這個數字就是 target 要的，只要 Push 留下來

ans.push_back("Push");
now++;

當前面的 while (now < i) 結束時，代表現在一定有：

now == i

這時這個數字就是 target 需要的，所以不能 pop 掉，只要做一次 "Push" 把它留下來即可。

接著 now++，表示串流繼續往後。

5. 為什麼做到 target 最後一個數字就可以停

題目規定：

只要 stack 中的元素已經等於 target
就要立刻停止
不能再繼續讀新的串流數字

而這份程式剛好就是只處理到 target 的最後一個元素為止。

所以當 for (int i : target) 跑完後：

stack 裡留下的數字就正好是 target
不會再多讀任何不需要的數字

這也符合題目要求。

6. 最後回傳操作序列

return ans;

當整個 target 都建立完成後，ans 裡記錄的就是完整合法操作序列，直接回傳即可。

⏱️ 複雜度

設 m = target.length，並設 target[m - 1] 為 target 的最後一個元素。

時間複雜度：O(target[m - 1])
串流從 1 一路模擬到 target 的最後一個值，每個數字最多處理一次。
空間複雜度：O(target[m - 1])
最多需要記錄從 1 到 target 最後一個值所對應的操作序列。

💻 程式碼實作

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        int now = 1;
        vector<string> ans;
        for (int i : target) {
            while (now < i) {
                ans.push_back("Push");
                ans.push_back("Pop");
                now++;
            }
            ans.push_back("Push");
            now++;
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/build-an-array-with-stack-operations/