[LeetCode] 3362. Zero Array Transformation III

https://leetcode.com/problems/zero-array-transformation-iii/description/?envType=daily-question&envId=2025-05-22

leetcode - Zero Array Transformation III

문제 유형: 정렬, 우선순위 큐

문제 난이도: Medium

 

문제

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.

 

queries[li, ri]의 2D 쿼리배열과 정수 배열 nums가 주어집니다.

각 queries[i]는 다음의 동작을 nums에 적용합니다:

• [l, r]의 범위에서 최대 1을 빼기
• 각각 요소별로 독립적으로

영배열은 모든 요소가 0일 배열을 말합니다.

영배열을 만들게 하면서 가장 많이 쿼리를 삭제하는 경우의 개수를 구하시오. 애초에 영배열 만들기가 안되면, -1로 반환하시오.

 

풀이

[l, r]중에서, l을 기점으로 오름차순 정렬하고, r을 기점으로 최대 힙을 만들어준다.

변화량의 반영배열 darr도 만들어준다.

 

0 ~ n의 각각의 i를 읽으면서, 만약 이번 queries[j][0]이 i와 같다면, pq에 범위끝인 queries[j][1]을 삽입시킨다. 이를 계속한다..

 

순차적으로 nums의 요수를 읽으며, nums[i]부터 시작하는 구간들은 끝나는 시간+1을  저장하면 된다.

그러고, 누적으로 빼는 량을 추적하는 변수 d에 매번 nums[l]와 nums[r+1]에 변화량을 저장시킨다.

d가 nums[i]보다 부족한동안, 최대 힙에서 계속요소를 빼서 쿼리를 소비한다. 만약 뭐리를 모두 소비하고도 d가 nums[i]보다 작아서 해결하지 못한다면, -1을 리턴한다.

 

무사히 모든 배열 순회가 끝나면, 최대 힙 큐의 사이즈를 리턴한다. 최대 힙에는 소비되지 않은 것들이 여전히 남아있다.

 

코드

C++

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

        return pq.size();
    }
};

 

Go

import (
    "container/heap"
    "sort"
)

type PriorityQueue []int
func(pq PriorityQueue) Len() int { return len(pq) }
func(pq PriorityQueue) Less(i, j int) bool {return pq[i] > pq[j]}
func(pq PriorityQueue) Swap(i, j int) {pq[i], pq[j] = pq[j], pq[i]}

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(int))
}
func(pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0:n-1]
    return x
}

func maxRemoval(nums []int, queries [][]int) int {
    pq := &PriorityQueue{} 
    heap.Init(pq)
    sort.Slice(queries, func(i, j int) bool {
        return queries[i][0] < queries[j][0]
    })
    darr := make([]int, len(nums)+1)
    d := 0
    j := 0
    for i := 0; i < len(nums); i++ {
        d += darr[i]
        for j < len(queries) && queries[j][0] == i {
            heap.Push(pq, queries[j][1])
            j++
        }
        for d < nums[i] && pq.Len() > 0 {
            end := heap.Pop(pq).(int)
            if end < i {
                heap.Push(pq, end)
                break
            }
            d++
            darr[end+1]--
        }
        if d < nums[i] {
            return -1
        }
    }

    return pq.Len()
}

 

Python

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

        return len(heap)