LeetCode 1705. [Python] Maximum Number of Eaten Apples
原题链接
中等
作者:
徐辰潇
,
2021-01-02 23:23:14
,
所有人可见
,
阅读 696
class Solution:
def eatenApples(self, apples: List[int], days: List[int]) -> int:
# TC: O(n log n) n = len(apples)
# SC: O(n)
#Use heap to store information of when the apples in given certain day will rot in the future.
Heap = []
res = 0
for i in range(len(days)):
if apples[i] > 0:
rotten_day = i + days[i]
heapq.heappush(Heap, [rotten_day, apples[i]])
while(len(Heap) > 0 and Heap[0][0] <= i):
heapq.heappop(Heap)
if len(Heap) > 0:
ele = heapq.heappop(Heap)
ele[1] = ele[1] - 1
if ele[1] > 0:
heapq.heappush(Heap, ele)
res += 1
i += 1
while(len(Heap) > 0):
if Heap[0][0] > i:
res += 1
i += 1
ele = heapq.heappop(Heap)
ele[1] = ele[1] - 1
if ele[1] > 0:
heapq.heappush(Heap, ele)
else:
heapq.heappop(Heap)
return res