題目資訊

題目編號: 3356
題目連結: Zero Array Transformation II
主題: Array, Binary Search, Prefix Sum

題目敘述

您有一個長度為 $n$ 的整數陣列 nums 和一個二維陣列 queries，其中 $queries[i] = [l_i, r_i, val_i]`。

每個 queries[i] 代表對 nums 的以下操作：

將 nums 中範圍 $[l_i, r_i]$ 內的每個索引處的值減少最多 $val_i$。
每個值減少的數量可以獨立為每個索引選擇。

零陣列是一個所有元素都等於 0 的陣列。

返回可能的最小非負值 $k$，使得在按順序處理前 $k$ 個查詢後，nums 成為零陣列。如果不存在這樣的 $k$，則返回 -1。

範例 1:

輸入： nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]

輸出： 2

解釋：

對於 i = 0 (l = 0, r = 2, val = 1):
- 分別減少索引 [0, 1, 2] 處的值 [1, 0, 1]。
- 陣列將變為 [1, 0, 1]。
對於 i = 1 (l = 0, r = 2, val = 1):
- 分別減少索引 [0, 1, 2] 處的值 [1, 0, 1]。
- 陣列將變為 [0, 0, 0]，這是一個零陣列。因此，$k$ 的最小值為 2。

範例 2:

輸入： nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]

輸出： -1

解釋：

對於 i = 0 (l = 1, r = 3, val = 2):
- 分別減少索引 [1, 2, 3] 處的值 [2, 2, 1]。
- 陣列將變為 [4, 1, 0, 0]。
對於 i = 1 (l = 0, r = 2, val = 1):
- 分別減少索引 [0, 1, 2] 處的值 [1, 1, 0]。
- 陣列將變為 [3, 0, 0, 0]，這不是一個零陣列。

限制條件：

$1 \leq nums.length \leq 10^5$
$0 \leq nums[i] \leq 5 \times 10^5$
$1 \leq queries.length \leq 10^5$
$queries[i].length == 3$
$0 \leq l_i \leq r_i < nums.length$
$1 \leq val_i \leq 5$

直覺

這個問題要求我們決定將整數數組 nums 轉化為零數組所需的最小查詢數目。每個查詢可以在一定限度內，獨立地減少特定索引處的值。經過仔細觀察，我們可以利用差分數組技術來有效地應用這些範圍更新，並快速檢查在每個查詢限制內的轉化是否可行。這引導我們想到可以通過二分搜尋查詢數量，以識別實現零數組所需的最少查詢數。

解法

差分數組技術:
- 我們使用大小為 n + 1 的差分數組 diff 來方便進行常數時間的範圍更新。這種技術有助於有效地應用多個範圍更新操作。
用於驗證的 Lambda 函式:
- 我們定義了一個 lambda 函式 canZeroOut(mid)，用來評估在前 mid 個查詢是否可以將 nums 轉化為零數組。
- 對於給定的 mid，迭代前 mid 個查詢，並在差分數組 diff 中更新，在起始索引處遞增，並在 endIndex + 1 處遞減。這標記了一個操作範圍的開始和結束。
可行性檢查:
- 使用變量 currentSum 來追踪應用在 nums 每個元素上的累計減值效果。
- 遍歷 nums 數組，根據 diff 的值更新 currentSum。如果在任何一個索引處累計減值 (currentSum) 小於對應的 nums 元素值，則返回 false，因為在給定的 mid 下無法將該元素歸零。
- 如果對所有索引都可行，則返回 true。
二分搜尋:
- 對 mid 進行二分搜尋，從 0 開始到 m + 1，其中 m 是查詢數量。
- 利用二分搜尋有效地找到最小的 mid 值，使得前 mid 個查詢能夠歸零整個數組。
- 根據可行性檢查調整搜尋範圍：如果 canZeroOut(mid) 為 true，則探索較小的 mid；否則，增加 mid。
結果評估:
- 如果二分搜尋結果 low 超過了 m，說明沒有有效的查詢順序可以將 nums 歸零，則返回 -1。
- 否則，返回 low，這表示所需的最小查詢數量。

整個方法圍繞著有效地處理範圍操作和利用二分搜尋，以在給定制約條件下最小化計算開銷。

程式碼

C++

class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int m = queries.size(); // 查詢次數
        int n = nums.size();    // nums 陣列的長度

        // Lambda 函數以判斷前 'mid' 個查詢是否能將陣列歸零
        auto canZeroOut = [&](int mid) -> bool {
            vector<long long> diff(n + 1, 0); // 差分陣列，用於高效地進行區間更新

            // 將前 'mid' 個查詢應用到差分陣列中
            for (int i = 0; i < mid; i++) {
                int startIndex = queries[i][0];
                int endIndex = queries[i][1];
                int val = queries[i][2];

                diff[startIndex] += val;
                if (endIndex + 1 < n) {
                    diff[endIndex + 1] -= val;
                }
            }

            long long currentSum = 0;
            // 檢查在應用這些更新後，nums 中的所有元素是否歸零
            for (int j = 0; j < n; j++) {
                currentSum += diff[j];
                // 如果當前累積的減量不足以將元素歸零，返回 false
                if (currentSum < nums[j]) {
                    return false;
                }
            }
            return true;
        };

        // 二分搜尋以找到能將陣列歸零的最小查詢數量
        int low = 0, high = m + 1; // 以多一個的 m 開始，以處理不存在有效 k 的情況
        while (low < high) {
            int mid = low + (high - low) / 2;
            // 如果前 'mid' 個查詢能將陣列歸零，則尋找較小的 'mid'
            if (canZeroOut(mid)) {
                high = mid;
            } else { // 否則，尋找較大的 'mid'
                low = mid + 1;
            }
        }

        // 如果 low 大於查詢次數，表明未找到有效的 k
        return (low > m) ? -1 : low;
    }
};

Python

class Solution:
    def minZeroArray(self, nums, queries):
        m = len(queries)  # 查詢數量
        n = len(nums)     # nums 陣列的長度

        # Lambda 函數，判斷前 'mid' 筆查詢能否使陣列歸零
        def canZeroOut(mid):
            diff = [0] * (n + 1)  # 差分陣列，用來高效地進行區間更新

            # 將前 'mid' 筆查詢應用到差分陣列
            for i in range(mid):
                startIndex = queries[i][0]
                endIndex = queries[i][1]
                val = queries[i][2]

                diff[startIndex] += val
                if endIndex + 1 < n:
                    diff[endIndex + 1] -= val

            currentSum = 0
            # 檢查應用完這些更新後，所有 nums 中的元素是否被歸零
            for j in range(n):
                currentSum += diff[j]
                # 如果當前累積的減量不足以將元素歸零，返回 false
                if currentSum < nums[j]:
                    return False
            return True

        # 二分搜尋找到能使陣列歸零的最小查詢數量
        low, high = 0, m + 1  # 從比 m 多一開始以處理不存在有效 k 的情況
        while low < high:
            mid = low + (high - low) // 2
            # 如果前 'mid' 筆查詢能使陣列歸零，搜尋更小的 'mid'
            if canZeroOut(mid):
                high = mid
            else:  # 否則搜索更大的 'mid'
                low = mid + 1

        # 如果 low 大於查詢數量，則表示沒有找到有效的 k
        return -1 if low > m else low

複雜度分析

時間複雜度: $O((n + m) \log m)$
此解法的時間複雜度包含兩個主要部分：
1. 查詢的二分搜尋：二分搜尋演算法試圖找到將 nums 歸零所需的最小查詢數量 $k$。二分搜尋的時間複雜度為 $O(\log m)$，其中 $m$ 是查詢的數量。
2. 區間更新與驗證：在二分搜尋中的每次檢查，演算法藉由使用基於差分數組的區間更新技術，需花費 $O(n)$ 的時間以在 nums 陣列上應用 $k$ 次查詢。
因此，在二分搜尋的每次迭代中，我們執行 $O(n)$ 的操作，得到總時間複雜度為 $O((n + m) \log m)$。
空間複雜度: $O(n)$
空間複雜度主要來自於使用大小為 $n + 1$ 的差分數組 diff。此數組用來在檢查一組給定的查詢是否可以將 nums 歸零時，進行有效的區間更新。因此，空間複雜度為 $O(n)$。

CS Note
En

Leetcode 3356. Zero Array Transformation II

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析