Medium

题目描述

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri, vali]。

每个 queries[i] 表示对 nums 执行以下操作：

  • 将 nums 中范围 [li, ri] 内每个下标的值减少至多 vali。
  • 每个下标减少的值可以独立选择。

零数组是所有元素都等于 0 的数组。

返回使 nums 变为零数组所需的最小非负整数 k，即按顺序处理前 k 个查询后 nums 变为零数组。如果不存在这样的 k，返回 -1。

示例 1：

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

输出：2

示例 2：

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

输出：-1

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 5 * 10^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 3
  • 0 <= li <= ri < nums.length
  • 1 <= vali <= 5

解题思路

这道题要求找到最小的查询数量 k，使得执行前 k 个查询后数组变为零数组。

核心思路：

  1. 二分查找答案：k 的取值范围是 [0, queries.length]，具有单调性。如果使用 k 个查询能让数组变零，那么使用 k+1 个查询也一定能让数组变零。因此可以用二分查找找到最小的 k。

  2. 差分数组优化区间更新：对于给定的 k 个查询，需要高效地计算每个位置最多能减少多少。使用差分数组可以将区间更新操作从 O(n) 优化到 O(1)，总体计算前缀和的时间复杂度为 O(n)。

  3. 检查可行性：对于前 k 个查询，计算每个位置能减少的最大值，然后检查是否足以让对应的 nums[i] 变为 0。

算法流程：

  • 二分查找 k 的值
  • 对于每个候选的 k，使用差分数组计算前 k 个查询能提供的最大减少量
  • 检查每个位置的减少量是否不小于对应的 nums[i]
  • 如果所有位置都满足条件，说明这个 k 可行，尝试更小的 k；否则需要更大的 k

时间复杂度：O(log(queries.length) × n)，空间复杂度：O(n)。

代码实现

class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int m = queries.size();
        
        auto canMakeZero = [&](int k) -> bool {
            vector<int> diff(n + 1, 0);
            
            // 使用差分数组处理前k个查询
            for (int i = 0; i < k; i++) {
                int l = queries[i][0], r = queries[i][1], val = queries[i][2];
                diff[l] += val;
                diff[r + 1] -= val;
            }
            
            // 计算每个位置能减少的最大值
            int reduction = 0;
            for (int i = 0; i < n; i++) {
                reduction += diff[i];
                if (reduction < nums[i]) {
                    return false;
                }
            }
            return true;
        };
        
        int left = 0, right = m, result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (canMakeZero(mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        m = len(queries)
        
        def can_make_zero(k):
            diff = [0] * (n + 1)
            
            # 使用差分数组处理前k个查询
            for i in range(k):
                l, r, val = queries[i]
                diff[l] += val
                diff[r + 1] -= val
            
            # 计算每个位置能减少的最大值
            reduction = 0
            for i in range(n):
                reduction += diff[i]
                if reduction < nums[i]:
                    return False
            return True
        
        left, right = 0, m
        result = -1
        
        while left <= right:
            mid = (left + right) // 2
            
            if can_make_zero(mid):
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return result

public class Solution {
    public int MinZeroArray(int[] nums, int[][] queries) {
        int n = nums.Length;
        int m = queries.Length;
        
        bool CanMakeZero(int k) {
            int[] diff = new int[n + 1];
            
            // 使用差分数组处理前k个查询
            for (int i = 0; i < k; i++) {
                int l = queries[i][0], r = queries[i][1], val = queries[i][2];
                diff[l] += val;
                diff[r + 1] -= val;
            }
            
            // 计算每个位置能减少的最大值
            int reduction = 0;
            for (int i = 0; i < n; i++) {
                reduction += diff[i];
                if (reduction < nums[i]) {
                    return false;
                }
            }
            return true;
        }
        
        int left = 0, right = m, result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (CanMakeZero(mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
}

var minZeroArray = function(nums, queries) {
    const n = nums.length;
    const m = queries.length;
    
    const canMakeZero = (k) => {
        const diff = new Array(n + 1).fill(0);
        
        // 使用差分数组处理前k个查询
        for (let i = 0; i < k; i++) {
            const [l, r, val] = queries[i];
            diff[l] += val;
            diff[r + 1] -= val;
        }
        
        // 计算每个位置能减少的最大值
        let reduction = 0;
        for (let i = 0; i < n; i++) {
            reduction += diff[i];
            if (reduction < nums[i]) {
                return false;
            }
        }
        return true;
    };
    
    let left = 0, right = m, result = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (canMakeZero(mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(log m × n)，其中 m 是查询数量，n 是数组长度
空间复杂度O(n)，用于存储差分数组

相关题目