Medium

题目描述

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

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

  • 从 nums 中选择范围 [li, ri] 内的一个索引子集
  • 将每个选定索引处的值精确减少 vali

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

返回最小可能的非负值 k，使得在按顺序处理前 k 个查询后，nums 变成零数组。如果不存在这样的 k，返回 -1。

示例 1：

输入：nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]
输出：2
解释：
- 查询 0 (l = 0, r = 2, val = 1)：将索引 [0, 2] 的值减 1，数组变为 [1, 0, 1]
- 查询 1 (l = 0, r = 2, val = 1)：将索引 [0, 2] 的值减 1，数组变为 [0, 0, 0]，这是零数组
因此最小 k 值为 2。

示例 2：

输入：nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]
输出：-1
解释：即使执行所有查询也无法使 nums 变成零数组。

示例 3：

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

约束条件：

  • 1 <= nums.length <= 10
  • 0 <= nums[i] <= 1000
  • 1 <= queries.length <= 1000
  • queries[i] = [li, ri, vali]
  • 0 <= li <= ri < nums.length
  • 1 <= vali <= 10

解题思路

这道题要求找到最少需要执行多少个查询才能将数组变为零数组。关键思路是：

核心思想： 使用二分搜索 + 动态规划验证。对于给定的 k 个查询，需要验证能否将数组变为零数组。

算法步骤：

  1. 二分搜索答案： 对查询个数 k 进行二分搜索，范围是 [0, queries.length]

  2. 可行性检查： 对于每个可能的 k，检查前 k 个查询是否能将数组变为零数组

  3. 动态规划验证： 对于数组的每个位置 i，找出所有能影响该位置的查询（即满足 li ≤ i ≤ ri 的查询），然后使用背包问题的思想，判断这些查询的 val 值能否组合成 nums[i]

  4. 背包DP实现： 对于每个位置 i，设 dp[j] 表示是否能用可用查询组合出和为 j。初始化 dp[0] = true，对于每个查询的 val 值，更新 dp 数组

  5. 验证结果： 如果对于所有位置 i，都存在 dp[nums[i]] = true，则说明前 k 个查询可以将数组变为零数组

优化要点：

  • 由于数组长度最多为 10，可以用位运算优化状态表示
  • 每个位置独立验证，降低复杂度

代码实现

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 {
            for (int i = 0; i < n; i++) {
                if (nums[i] == 0) continue;
                
                vector<int> vals;
                for (int j = 0; j < k; j++) {
                    if (queries[j][0] <= i && i <= queries[j][1]) {
                        vals.push_back(queries[j][2]);
                    }
                }
                
                vector<bool> dp(nums[i] + 1, false);
                dp[0] = true;
                
                for (int val : vals) {
                    for (int j = nums[i]; j >= val; j--) {
                        if (dp[j - val]) dp[j] = true;
                    }
                }
                
                if (!dp[nums[i]]) return false;
            }
            return true;
        };
        
        int left = 0, right = m;
        int 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):
            for i in range(n):
                if nums[i] == 0:
                    continue
                
                vals = []
                for j in range(k):
                    if queries[j][0] <= i <= queries[j][1]:
                        vals.append(queries[j][2])
                
                dp = [False] * (nums[i] + 1)
                dp[0] = True
                
                for val in vals:
                    for j in range(nums[i], val - 1, -1):
                        if dp[j - val]:
                            dp[j] = True
                
                if not dp[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) {
            for (int i = 0; i < n; i++) {
                if (nums[i] == 0) continue;
                
                var vals = new List<int>();
                for (int j = 0; j < k; j++) {
                    if (queries[j][0] <= i && i <= queries[j][1]) {
                        vals.Add(queries[j][2]);
                    }
                }
                
                var dp = new bool[nums[i] + 1];
                dp[0] = true;
                
                foreach (int val in vals) {
                    for (int j = nums[i]; j >= val; j--) {
                        if (dp[j - val]) dp[j] = true;
                    }
                }
                
                if (!dp[nums[i]]) return false;
            }
            return true;
        }
        
        int left = 0, right = m;
        int 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;
    
    function canMakeZero(k) {
        const arr = [...nums];
        
        for (let i = 0; i < k; i++) {
            const [l, r, val] = queries[i];
            
            // For each position in range [l, r], we want to reduce it by val
            // But we need to be greedy - reduce the largest values first
            const positions = [];
            for (let j = l; j <= r; j++) {
                if (arr[j] > 0) {
                    positions.push(j);
                }
            }
            
            // Sort by value (descending) to be greedy
            positions.sort((a, b) => arr[b] - arr[a]);
            
            // Apply reduction of val to each position
            for (let j of positions) {
                const reduction = Math.min(arr[j], val);
                arr[j] -= reduction;
            }
        }
        
        return arr.every(x => x === 0);
    }
    
    let left = 0, right = queries.length;
    let 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 × k × V)，其中 m 是查询数，n 是数组长度，k 是平均每个位置受影响的查询数，V 是数组元素的最大值
空间复杂度O(V)，用于动态规划数组

相关题目