作者:
Rushia (みけねこ的鼻屎)
2025-03-14 00:25:59https://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: