2025-06-12：零数组变换Ⅲ。用go语言，给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中每个 queries[i] = [li, ri] 表示对 nums 的一个操作。

每个操作表示：在索引范围 [li, ri] 内的元素，每个元素最多可以减少 1。需要注意的是，区间内每个元素减少的次数是独立计算的。

定义“零数组”为所有元素均为 0 的数组。

要求你找出最多可以从 queries 中删除多少个操作，使得剩下的操作仍然能够将 nums 减至零数组。如果无论如何都无法将 nums 变成零数组，则返回 -1。

1 <= nums.length <= 100000。

0 <= nums[i] <= 100000。

1 <= queries.length <= 100000。

queries[i].length == 2。

0 <= li <= ri < nums.length。

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

输出：2。

解释：

可以删除 queries[2] 和 queries[3] 。

题目来自力扣3362。

解题思路

1. 贪心策略：

   • 我们希望尽可能多地删除 queries 中的操作，因此应该优先保留那些覆盖范围更广（即 [li, ri] 区间更长）的操作，因为它们可以同时对多个 nums[i] 进行减 1 操作，减少对额外操作的需求。
   • 因此，我们可以按照 li（左端点）从小到大排序 queries，并在处理时优先选择 ri（右端点）较大的操作（使用最大堆）。

2. 差分数组优化：

   • 直接对 nums 进行减 1 操作会导致时间复杂度较高（最坏情况 O(n²)），因此采用差分数组（deltaArray）来记录每个位置需要减 1 的次数，从而在 O(1) 时间内完成区间更新。

3. 处理流程：

   • 排序 queries：按 li 从小到大排序，以便按顺序处理。
   • 最大堆（优先队列）：用于存储当前可用的 ri（右端点），每次选择最大的 ri 进行操作。
   • 遍历 nums：
     • 对于每个 nums[i]，先应用差分数组的累计影响（即 operations）。
     • 将所有 li == i 的 queries 加入堆（表示这些操作当前可用）。
     • 如果 nums[i] 还未减到 0，则从堆中取出最大的 ri 进行操作（即 operations++，并在 deltaArray[ri+1] 记录回退）。
     • 如果 nums[i] 仍然无法减到 0，说明无法完成，返回 -1。
   • 最终，堆中剩余的操作就是可以删除的。

详细步骤

1. 预处理 queries：

   • 按 li 从小到大排序，使得我们可以按顺序处理每个 nums[i] 时，一次性加入所有 li == i 的操作。

2. 初始化数据结构：

   • 差分数组 deltaArray：长度为 n+1，用于记录区间操作的累计影响。
   • 最大堆 pq：存储当前可用的 ri（右端点），优先取最大的 ri。
   • 操作计数器 operations：记录当前 nums[i] 已经减 1 的次数。

3. 遍历 nums：

   • 对于每个 i（从左到右）：
     • 应用差分数组的影响：operations += deltaArray[i]。
     • 将所有 li == i 的 queries 加入堆（heap.Push(pq, ri)）。
     • 如果 nums[i] - operations > 0（即还需要减 1），则从堆中取出最大的 ri：
       • 每取出一个 ri，operations++（表示对该区间 [i, ri] 执行一次减 1）。
       • 在 deltaArray[ri+1]--（表示后续 i > ri 时不再受此操作影响）。
     • 如果 nums[i] 仍然无法减到 0，返回 -1。

4. 返回结果：

   • 最终堆中剩余的操作就是可以删除的，返回 pq.Len()。

时间复杂度

• 排序 queries：O(m log m)，其中 m 是 queries 的长度。
• 堆操作：每个 queries[i] 最多入堆和出堆一次，每次堆操作 O(log m)，总复杂度 O(m log m)。
• 遍历 nums 和差分数组处理：O(n + m)。
• 总时间复杂度：O(m log m + n + m) = O(m log m + n)。

空间复杂度

• 差分数组 deltaArray：O(n)。
• 最大堆 pq：O(m)。
• 总空间复杂度：O(n + m)。

Go完整代码如下：

.

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

func maxRemoval(nums []int, queries [][]int) int {
	sort.Slice(queries, func(i, j int) bool {
		return queries[i][0] < queries[j][0]
	})
	pq := &Heap{}
	heap.Init(pq)
	deltaArray := make([]int, len(nums)+1)
	operations := 0

	for i, j := 0, 0; i < len(nums); i++ {
		operations += deltaArray[i]
		for j < len(queries) && queries[j][0] == i {
			heap.Push(pq, queries[j][1])
			j++
		}
		for operations < nums[i] && pq.Len() > 0 && (*pq)[0] >= i {
			operations += 1
			deltaArray[heap.Pop(pq).(int)+1] -= 1
		}
		if operations < nums[i] {
			return -1
		}
	}
	return pq.Len()
}

type Heap []int

func (h Heap) Len() int {
	return len(h)
}

func (h Heap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h Heap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *Heap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *Heap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	nums := []int{1, 1, 1, 1}
	queries := [][]int{{1, 3}, {0, 2}, {1, 3}, {1, 2}}
	fmt.Println(maxRemoval(nums, queries))
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

import heapq

def max_removal(nums, queries):
    # 按左端点升序排序
    queries.sort(key=lambda x: x[0])
    pq = []
    n = len(nums)
    delta_array = [0] * (n + 1)
    operations = 0
    j = 0

    for i in range(n):
        operations += delta_array[i]
        # 将左端点等于i的区间右端点加入堆，Python默认小顶堆，这里存入右端点，负号处理实现大顶堆
        while j < len(queries) and queries[j][0] == i:
            # 这里我们需要最大堆，而heapq是小顶堆，存入负值实现
            heapq.heappush(pq, -queries[j][1])
            j += 1
        # 对应代码中，当operations < nums[i]且堆顶区间右端点大于等于 i，继续使用区间
        while operations < nums[i] and pq and -pq[0] >= i:
            operations += 1
            end = -heapq.heappop(pq)
            delta_array[end + 1] -= 1
        if operations < nums[i]:
            return -1
    return len(pq)

if __name__ == "__main__":
    nums = [1, 1, 1, 1]
    queries = [[1, 3], [0, 2], [1, 3], [1, 2]]
    print(max_removal(nums, queries))