2025-06-12：零数组变换Ⅲ。用go语言，给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中每

福大大架构师每日一题

发布于 2025-06-12 11:03:47

7300

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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][] < queries[j][]
    })
    pq := &Heap{}
    heap.Init(pq)
    deltaArray := make([]int, len(nums)+)
    operations := 

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

type Heap []int

func (h Heap) Len() int {
    returnlen(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[ : n-1]
    return x
}

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

Python完整代码如下：

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

import heapq

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

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

if __name__ == "__main__":
    nums = [, , , ]
    queries = [[, ], [, ], [, ], [, ]]
    print(max_removal(nums, queries))