Re: [閒聊] 每日leetcode
1508. Range Sum of Sorted Subarray Sums
## 思路
建heap 存range_sum 跟 idx
每次pop出來的值再加上nums[idx+1]丟回去heap
然後加總left~right次pop的range sum
## Complexity
Time: O(max(N, right) log N) = O(N^2 logN)
Space: O(N)
```python
class Solution:
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
MOD = 1_000_000_007
# O(N)
pq = [(num, idx) for idx, num in enumerate(nums)] # (num, idx)
heapq.heapify(pq)
# O(max(N, right) log N)
ans = 0
for i in range(1, right+1):
num, idx = heapq.heappop(pq)
if i >= left:
ans = (ans + num) % MOD
if idx + 1 < n:
heapq.heappush(pq, (num + nums[idx+1], idx+1))
return ans
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.182 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722744751.A.CC8.html
推
08/04 12:16,
1年前
, 1F
08/04 12:16, 1F
討論串 (同標題文章)
完整討論串 (本文為第 632 之 1552 篇)：