問題背景
給你一個長度為 n n n 的整數數組 n u m s nums nums 和一個二維數組 q u e r i e s queries queries，其中 q u e r i e s [ i ] = [ l i , r i ] queries[i] = [l_i, r_i] queries[i]=[li?,ri?]。
每一個 q u e r i e s [ i ] queries[i] queries[i] 表示對于 n u m s nums nums 的以下操作：
- 將 n u m s nums nums 中下標在范圍 [ l i , r i ] [l_i, r_i] [li?,ri?] 之間的每一個元素 最多 減少 1 1 1。
- 坐標范圍內每一個元素減少的值相互 獨立 。
零數組 指的是一個數組里所有元素都等于 0 0 0。
請你返回 最多 可以從 q u e r i e s queries queries 中刪除多少個元素，使得 q u e r i e s queries queries 中剩下的元素仍然能將 n u m s nums nums 變為一個 零數組 。如果無法將 n u m s nums nums 變為一個 零數組 ，返回 ? 1 -1 ?1。
數據約束
- 1 ≤ n u m s . l e n g t h ≤ 10 5 1 \le nums.length \le 10 ^ 5 1≤nums.length≤105
- 0 ≤ n u m s [ i ] ≤ 10 5 0 \le nums[i] \le 10 ^ 5 0≤nums[i]≤105
- 1 ≤ q u e r i e s . l e n g t h ≤ 10 5 1 \le queries.length \le 10 ^ 5 1≤queries.length≤105
- q u e r i e s [ i ] . l e n g t h = 2 queries[i].length = 2 queries[i].length=2
- 0 ≤ l i ≤ r i < n u m s . l e n g t h 0 \le l_i \le r_i < nums.length 0≤li?≤ri?<nums.length
解題過程
本題與 零數組變換 II 的區別在于數組可以不按順序使用，那么一個比較明顯的貪心思路是，在每個位置上選擇可能的范圍最大的數組，這樣后續某些位置上就可以不必操作，提高效率。
每個位置上的最大右端點，可以用最大堆來維護。
具體實現
class Solution {public int maxRemoval(int[] nums, int[][] queries) {Arrays.sort(queries, (o1, o2) -> o1[0] - o2[0]);PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);int n = nums.length;int[] diff = new int[n + 1];int num = 0;int j = 0;for (int i = 0; i < n; i++) {num += diff[i];while (j < queries.length && queries[j][0] <= i) {heap.add(queries[j][1]);j++;}while (num < nums[i] && !heap.isEmpty() && heap.peek() >= i) {num++;diff[heap.poll() + 1]--;}if (num < nums[i]) {return -1;}}return heap.size();}
}
)
