Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間9月前 (2025/03/14 00:26)推噓1(1推 0噓 0→)

https://leetcode.com/problems/zero-array-transformation-ii/ 3356. Zero Array Transformation II 給你一個陣列nums，和一個陣列queries，queries[i] = [li, ri, vali]，我們可以按照 queries的順序對nums[li:ri]的任意索引減去vali，求出最少要幾次query才可以讓陣列的元素全為0，如果無法做到返回-1。思路: 1.要找一個最小的k滿足需求，很明顯的二分搜索題，只是check函數的設計很嚴格，直接一個一個減去會TLE，用前綴和會MLE，只能用差分數組處理，一次處理所有區間，把query都處理完後，還原差份數組本來的值，判斷是否每個值都小於等於0就好。 Java Code: --------------------------------------------------------------- class Solution { public int minZeroArray(int[] nums, int[][] queries) { int l = 0; int r = queries.length; while (l <= r) { int mid = (l + r)/2; if (check(nums, queries, mid)) { r = mid - 1; } else { l = mid + 1; } } return l <= queries.length ? l : -1; } private boolean check(int[] nums, int[][] queries, int k) { int[] diff = new int[nums.length]; diff[0] = nums[0]; for (int i = 1; i < nums.length ; i++) { diff[i] = nums[i] - nums[i - 1]; } for (int i = 0; i < k; i++) { int from = queries[i][0]; int to = queries[i][1]; int val = -queries[i][2]; diff[from] += val; if (to + 1 < nums.length) { diff[to + 1] -= val; } } int sum = 0; for (int val : diff) { sum += val; if (sum > 0) { return false; } } return true; } } --------------------------------------------------------------- -- https://i.imgur.com/yRXNquY.jpeg