# Q2. Merge Adjacent Equal Elements

**練習日期：** 2026-02-08
**類型：** Weekly Contest 488

## 📘 題目敘述

給你一個整數陣列 `nums`。

你必須重複進行以下合併操作，直到再也無法產生變化為止：

如果目前陣列中存在任意一對相鄰且相等的元素，請選擇**最左邊**的那一對相鄰元素，並把它們替換成一個新元素，新元素的值等於它們的總和。

每次合併後，陣列長度會減少 1。你要在更新後的陣列上持續重複操作，直到無法再合併。

請回傳所有可能的合併完成後的最終陣列。

### 條件限制

* `1 <= nums.length <= 10^5`
* `1 <= nums[i] <= 10^5`

## 🧠 解題思路

題目規則有一個很麻煩的地方：它強調「每次一定要合併最左邊那一對相鄰相等元素」。如果真的照規則每次去找最左邊相等對、合併一次、再重找一次，最壞會變成很多次掃描，容易超時。

我這份寫法的想法是：用一個「堆疊」來模擬合併後的結果，而且可以自然保證「最左邊優先」的效果。

我從左到右讀 `nums`，把結果維護在 `st` 裡，讓 `st` 代表「目前已處理完的前綴，在完整合併規則下會變成什麼樣子」。

當我拿到一個新數字 `now`（一開始就是 `nums[i]`），我只需要看 `st` 的最後一個元素：

* 如果 `st.back() != now`，代表新元素放進去不會立刻產生相鄰相等，就直接 push 進 `st`。
* 如果 `st.back() == now`，代表形成了「相鄰相等」這一對，而且這一對一定是目前能合併的最左邊之一（因為我們是從左到右建立結果的），所以我就把 `st.back()` pop 掉，並把 `now` 變成 `now * 2`（因為相等相加就是翻倍），然後再繼續檢查：新的 `now` 可能又會跟更前面的元素相等，造成連鎖合併。

所以我用 `while (!st.empty() && st.back() == now)` 來處理這種連鎖合併，一次把所有會連鎖的合併做完，再把最後的 `now` 放回 `st`。

最後整個 `nums` 掃完後，`st` 就是最終陣列。

### 所有變數

* `nums`：題目輸入陣列
* `st`：用來模擬合併結果的堆疊（我用 `vector<long long>` 當 stack）
* `now`：目前正在處理、可能會一路翻倍合併的值

## 🪜 主要流程步驟

### 1. 用 `st` 維護「目前處理到這裡的最終狀態」

我建立一個 `vector<long long> st`，把它當作堆疊使用。`st` 裡存的就是目前已經處理完的前綴，經過題目規則完整合併後留下的序列。

---

### 2. 從左到右讀取每個元素，先把它當作 `now`

每讀到一個 `nums[i]`，我把它放到 `now`（用 `long long` 是因為合併會變大）。

---

### 3. 只要 `now` 跟 `st` 最後一個元素相等，就代表會合併

如果 `st.back() == now`，就表示形成相鄰相等的一對，依規則要合併，所以：

* `st.pop_back()` 把那個相等的左邊元素拿掉
* `now *= 2` 把合併後的結果更新成翻倍

這一步做完後，新的 `now` 可能又和更前面的 `st.back()` 相等，所以要用 while 連鎖合併，直到不能合併為止。

---

### 4. 連鎖合併結束後，把最後的 `now` 放回 `st`

當 while 結束，代表 `st` 目前最後一個元素不等於 `now`（或 `st` 已空），此時把 `now` push 回 `st`，表示這個位置的合併處理完成。

---

### 5. 全部處理完後回傳 `st`

當整個陣列都掃完，`st` 就是題目要求的最終陣列。

## 💻 程式碼實作

class Solution {
public:
    vector<long long> mergeAdjacent(vector<int>& nums) {
        vector<long long> st;
        for (int i : nums) {
            long long now = i;
            while (!st.empty() && st.back() == now) {
                st.pop_back();
                now *= 2;
            }
            st.push_back(now);
        }
        return st;
    }
};

## 🔗 題目連結
https://leetcode.com/contest/weekly-contest-488/problems/merge-adjacent-equal-elements/description/