題目: 3356. Zero Array Transformation II
難度: Medium
目前下列解法的時間複雜度: O( nums.length + queries.length )
題目說明
給定一堆位置區間 (queries) ，每個區間有一個值 val ，代表這個區間內的數字最多可以扣 val 。
問只需要用前幾個區間，就能把另外給定的陣列 (nums) 中的整數扣到 0 或負的。
解法：
1. 區間均質=記端點就好。開一條陣列紀錄每個位置可以扣的量比之前差多少。花費 O(queries.length) 的時間將所有區間丟進去，此時從位置 0 走到 nums.length-1 可以在總時間 O(nums.length) 知道每一格最多可以扣多少。
2. 如果某一格需要用到 k 個區間的 val 來扣，下一格就從 k 個開始繼續嘗試。
3. 綜合 1 與 2 ，在從位置 0 走到 nums.length-1 的過程中，從使用 0 個區間，慢慢增加用到的區間數 k 。如果都用完了還是沒扣完，回傳 -1 。
當然你用 binary search 硬爆也可以啦。 O( (nums.length + queries.length) * log(queries.length) )
沒有source code
難度: Medium
目前下列解法的時間複雜度: O( nums.length + queries.length )
題目說明
給定一堆位置區間 (queries) ，每個區間有一個值 val ，代表這個區間內的數字最多可以扣 val 。
問只需要用前幾個區間，就能把另外給定的陣列 (nums) 中的整數扣到 0 或負的。
解法：
1. 區間均質=記端點就好。開一條陣列紀錄每個位置可以扣的量比之前差多少。花費 O(queries.length) 的時間將所有區間丟進去，此時從位置 0 走到 nums.length-1 可以在總時間 O(nums.length) 知道每一格最多可以扣多少。
2. 如果某一格需要用到 k 個區間的 val 來扣，下一格就從 k 個開始繼續嘗試。
3. 綜合 1 與 2 ，在從位置 0 走到 nums.length-1 的過程中，從使用 0 個區間，慢慢增加用到的區間數 k 。如果都用完了還是沒扣完，回傳 -1 。
當然你用 binary search 硬爆也可以啦。 O( (nums.length + queries.length) * log(queries.length) )
沒有source code
