3362. Zero Array Transformation III

中文文档

Description

You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri].

Each queries[i] represents the following action on nums:

• Decrement the value at each index in the range [li, ri] in nums by at most 1.
• The amount by which the value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, return -1.

 

Example 1:

Input: nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]

Output: 1

Explanation:

After removing queries[2], nums can still be converted to a zero array.

• Using queries[0], decrement nums[0] and nums[2] by 1 and nums[1] by 0.
• Using queries[1], decrement nums[0] and nums[2] by 1 and nums[1] by 0.

Example 2:

Input: nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]

Output: 2

Explanation:

We can remove queries[2] and queries[3].

Example 3:

Input: nums = [1,2,3,4], queries = [[0,3]]

Output: -1

Explanation:

nums cannot be converted to a zero array even after using all the queries.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= li <= ri < nums.length

Solutions

Solution 1

Python3

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        queries.sort()
        pq = []
        d = [0] * (len(nums) + 1)
        s = j = 0
        for i, x in enumerate(nums):
            s += d[i]
            while j < len(queries) and queries[j][0] <= i:
                heappush(pq, -queries[j][1])
                j += 1
            while s < x and pq and -pq[0] >= i:
                s += 1
                d[-heappop(pq) + 1] -= 1
            if s < x:
                return -1
        return len(pq)

Java

class Solution {
    public int maxRemoval(int[] nums, int[][] queries) {
        Arrays.sort(queries, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int n = nums.length;
        int[] d = new int[n + 1];
        int s = 0, j = 0;
        for (int i = 0; i < n; i++) {
            s += d[i];
            while (j < queries.length && queries[j][0] <= i) {
                pq.offer(queries[j][1]);
                j++;
            }
            while (s < nums[i] && !pq.isEmpty() && pq.peek() >= i) {
                s++;
                d[pq.poll() + 1]--;
            }
            if (s < nums[i]) {
                return -1;
            }
        }
        return pq.size();
    }
}

C++

class Solution {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
        sort(queries.begin(), queries.end());
        priority_queue<int> pq;
        int n = nums.size();
        vector<int> d(n + 1, 0);
        int s = 0, j = 0;
        for (int i = 0; i < n; ++i) {
            s += d[i];
            while (j < queries.size() && queries[j][0] <= i) {
                pq.push(queries[j][1]);
                ++j;
            }
            while (s < nums[i] && !pq.empty() && pq.top() >= i) {
                ++s;
                int end = pq.top();
                pq.pop();
                --d[end + 1];
            }
            if (s < nums[i]) {
                return -1;
            }
        }
        return pq.size();
    }
};

Go

func maxRemoval(nums []int, queries [][]int) int {
	sort.Slice(queries, func(i, j int) bool {
		return queries[i][0] < queries[j][0]
	})

	var h hp
	heap.Init(&h)

	n := len(nums)
	d := make([]int, n+1)
	s, j := 0, 0

	for i := 0; i < n; i++ {
		s += d[i]
		for j < len(queries) && queries[j][0] <= i {
			heap.Push(&h, queries[j][1])
			j++
		}
		for s < nums[i] && h.Len() > 0 && h.IntSlice[0] >= i {
			s++
			end := heap.Pop(&h).(int)
			if end+1 < len(d) {
				d[end+1]--
			}
		}
		if s < nums[i] {
			return -1
		}
	}

	return h.Len()
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any)        { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

TypeScript

function maxRemoval(nums: number[], queries: number[][]): number {
    queries.sort((a, b) => a[0] - b[0]);
    const pq = new MaxPriorityQueue<number>();
    const n = nums.length;
    const d: number[] = Array(n + 1).fill(0);
    let [s, j] = [0, 0];
    for (let i = 0; i < n; i++) {
        s += d[i];
        while (j < queries.length && queries[j][0] <= i) {
            pq.enqueue(queries[j][1]);
            j++;
        }
        while (s < nums[i] && !pq.isEmpty() && pq.front() >= i) {
            s++;
            d[pq.dequeue() + 1]--;
        }
        if (s < nums[i]) {
            return -1;
        }
    }
    return pq.size();
}