Q1. Minimum Prefix Removal to Make Array Strictly Increasing

📘 題目敘述

給定一個整數陣列 nums。

你需要從 nums 中移除恰好一個前綴（prefix），這個前綴可以是空的。

請回傳一個整數，表示最少需要移除的前綴長度，使得剩下的陣列成為嚴格遞增（strictly increasing）。

如果一個陣列中，對於所有合法的 i，都滿足 nums[i] < nums[i + 1]，則稱該陣列為嚴格遞增。

條件限制

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

🧠 解題思路

我的想法是：

我想要留下來的「剩餘陣列」必須是嚴格遞增，所以我只要找出「最早可以開始變成嚴格遞增的地方」就好。

換句話說，我在從左到右掃描時，只要發現 nums[i] 沒有比前一個數字大（也就是 nums[i] <= last），那就代表：

如果我希望剩下的陣列從某個位置開始是嚴格遞增
那至少要把 prefix 移除到 i 這個位置之前
所以「需要移除的最短長度」至少要更新成 i

因此我一路掃描，記錄「最後一次破壞嚴格遞增的位置」，最後回傳那個位置 count，就是答案。

所有變數

last：上一個掃描到的數字（用來判斷目前 nums[i] 是否仍維持嚴格遞增）
count：目前推到的「最短要移除的 prefix 長度」（也就是最後一次違反嚴格遞增的索引 i）
i：掃描陣列的索引

🪜 主要流程步驟

1. 初始化

last = nums[0]：先把第一個數字當作比較基準
count = 0：預設移除長度為 0（代表可能本來就已經嚴格遞增）

2. 從左到右掃描整個陣列

每次看一個 nums[i]，做兩件事：

情況一：`nums[i] <= last`（破壞嚴格遞增）

這代表如果「剩下的陣列要從某個位置開始嚴格遞增」
那至少不能從 i 之前開始留下來
所以我更新：count = i

情況二：`nums[i] > last`（仍維持嚴格遞增）

代表目前還沒有破壞條件
count 不需要改動

不管是哪個情況，最後都會更新：

last = nums[i]：讓下一輪用新的 last 繼續比較

3. 回傳答案

掃描完後，count 就是「最短需要移除的 prefix 長度」
因為它代表「最後一次出現 nums[i] <= nums[i-1] 的位置」
把 prefix 移除到 count，剩下的尾巴就會是嚴格遞增

💻 程式碼實作

class Solution {
public:
    int minimumPrefixLength(vector<int>& nums) {
        int last = nums[0];
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= last) {
                count = i;
            }
            last = nums[i];
        }
        return count;
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-486/problems/minimum-prefix-removal-to-make-array-strictly-increasing/