Q3. Minimum Operations to Make Array Non Decreasing

📘 題目敘述

給定一個整數陣列 nums。

一次操作中，你可以選擇任意一段子陣列 nums[l..r]，並把這整段的每個元素都加上同一個正整數 x。

請回傳：要把整個陣列變成 non-decreasing 所需的最小總操作成本，也就是所有操作中選擇的 x 加總最小值。

條件限制

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

🧠 解題思路

我這題的想法是直接看每一對相鄰元素。

如果 nums[i - 1] <= nums[i]，那這一對本來就沒有問題。但如果 nums[i - 1] > nums[i]，那至少要把右邊這一側補高到不小於左邊，差多少就一定要補多少。

因此整體最小答案就是把所有下降的地方 nums[i - 1] - nums[i] 全部加起來。

所有變數

• ans：最後最小總操作成本
• n：陣列長度

🪜 主要流程步驟

1. 先處理只有一個元素的情況

if (n == 1) {
    return 0;
}

2. 從左到右檢查每一對相鄰元素

從索引 1 開始掃，去看每個 nums[i] 和前一個元素 nums[i - 1] 的關係。

3. 遇到下降時，把差值加進答案

if (nums[i - 1] > nums[i]) {
    ans += (nums[i - 1] - nums[i]);
}

4. 全部掃完後回傳答案

當整個陣列掃完之後，ans 裡面就是所有下降缺口的總和，也就是最少需要付出的操作成本。

⏱️ 複雜度

設 n = nums.length。

• 時間複雜度：O(n)
• 空間複雜度：O(1)

💻 程式碼實作

class Solution {
public:
    long long minOperations(vector<int>& nums) {
        long long ans = 0;
        int n = nums.size();
        if (n == 1) {
            return 0;
        }
        for (int i = 1; i < n; i++) {
            if (nums[i - 1] > nums[i]) {
                ans += (nums[i - 1] - nums[i]);
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-499/problems/minimum-operations-to-make-array-non-decreasing/