3818. 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

🧠 解題思路

我的想法是：只要找出「最後一次破壞嚴格遞增的位置」，那就是最短要移除的 prefix 長度。

• 掃描時若出現 nums[i] <= last，代表這個位置之前都不能保留
• 因此更新 count = i 作為最短要移除的長度

所有變數

• last：上一個掃描到的數字
• count：目前最短要移除的 prefix 長度
• i：掃描陣列的索引

🪜 主要流程步驟

1. 初始化

• last = nums[0]
• count = 0

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

• 如果 nums[i] <= last，更新 count = i
• 更新 last = nums[i]

3. 回傳答案

• 掃描完後回傳 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/problems/minimum-prefix-removal-to-make-array-strictly-increasing/