3507. Minimum Pair Removal to Sort Array I

📘 題目敘述

給定一個整數陣列 nums，你可以重複做以下操作任意次：

• 選擇 nums 中「相鄰且和最小」的那一對數字
• 若有多組相同的最小和，選最左邊那一組
• 把這一對相鄰數字用它們的總和取代（陣列長度 -1）

請回傳最少需要幾次操作，才能讓 nums 變成 non-decreasing（單調不下降）。

條件限制

• 1 <= nums.length <= 50
• -1000 <= nums[i] <= 1000

🧠 解題思路

我的想法是模擬題目的操作規則：每一步都選相鄰最小和（同和取最左），直到陣列已經 non-decreasing。

只要還存在 nums[i] > nums[i + 1]，就持續合併最小相鄰和的那一對並累加次數。

所有變數

• time：目前做了幾次合併（最後要回傳的答案）
• check：判斷陣列是否仍然不是 non-decreasing
• count：這一輪掃描時的最小相鄰和
• pos：最小相鄰和對應的左端索引（要合併的位置）

🪜 主要流程步驟

1. 反覆進行「掃描 + 合併」直到陣列變成 non-decreasing

• 用 while (check) 控制主流程，每一輪都先掃描再視情況合併

2. 掃描陣列找最小相鄰和並檢查是否已排序

• 只要看到 nums[i] > nums[i + 1]，就表示還沒排序好
• 同時更新最小相鄰和的位置（同和保留最左邊）

3. 若還沒排序好，合併最小相鄰和的那一對

• 用總和覆蓋左邊元素，刪掉右邊元素
• 操作次數 time++

4. 若已排序好則停止

• 當整個陣列已經 non-decreasing，回傳 time

💻 程式碼實作

class Solution {
public:
    int minimumPairRemoval(vector<int>& nums) {
        bool check = true;
        int time = 0;
        while (check) {
            int count = 2147483647;
            int pos = 0;
            if (nums.size() < 2) {
                return time;
            }
            check = false;
            for (int i = 0; i < nums.size() - 1; i++) {
                if (nums[i] > nums[i + 1]) {
                    check = true;
                }
                if (nums[i] + nums[i + 1] < count) {
                    pos = i;
                    count = nums[i] + nums[i + 1];
                }
            }
            if (check) {
                nums[pos] = nums[pos] + nums[pos + 1];
                nums.erase(nums.begin() + pos + 1);
                time++;
            }
        }
        return time;
    }
};

🔗 題目連結

https://leetcode.com/problems/minimum-pair-removal-to-sort-array-i/