題目描述
有一棵特殊的蘋果樹，一連 n 天，每天都可以長出若幹個蘋果。在第 i 天，樹上會長出 apples[i] 個蘋果，這些蘋果将會在 days[i] 天後（也就是說，第 i + days[i] 天時）腐爛，變得無法食用。也可能有那麼幾天，樹上不會長出新的蘋果，此時用 apples[i] == 0 且 days[i] == 0 表示。
你打算每天 最多 吃一個蘋果來保證營養均衡。注意，你可以在這 n 天之後繼續吃蘋果。
給你兩個長度為 n 的整數數組 days 和 apples，傳回你可以吃掉的蘋果的最大數目。
示例 1：
輸入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
輸出：7
解釋：你可以吃掉 7 個蘋果：
- 第一天，你吃掉第一天長出來的蘋果。
- 第二天，你吃掉一個第二天長出來的蘋果。
- 第三天，你吃掉一個第二天長出來的蘋果。過了這一天，第三天長出來的蘋果就已經腐爛了。
- 第四天到第七天，你吃的都是第四天長出來的蘋果。 示例 2：
輸入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
輸出：5
解釋：你可以吃掉 5 個蘋果：
- 第一天到第三天，你吃的都是第一天長出來的蘋果。
- 第四天和第五天不吃蘋果。
- 第六天和第七天，你吃的都是第六天長出來的蘋果。 提示：
- apples.length == n
- days.length == n
- 1 <= n <= 2 * 10⁴
- 0 <= apples[i], days[i] <= 2 * 10⁴
- 隻有在 apples[i] = 0 時，days[i] = 0 才成立
解決方案
方法一：貪心 + 優先隊列
為了将吃蘋果的數目最大化，應該使用貪心政策，在尚未腐爛的蘋果中優先選擇腐爛日期最早的蘋果。
為了得到腐爛日期最早的蘋果，可以使用優先隊列存儲每個蘋果的腐爛日期，優先隊列中最小的元素（即最早的腐爛日期）會最先被取出。由于數組 apples 和 days 的長度 n 最大為 2×10⁴，兩個數組中的每個元素最大為 2×10⁴，是以蘋果的總數最大可達 (2×10⁴)×(2×10⁴)=4×10^8。如果直接使用優先隊列存儲每個蘋果的腐爛日期，則會導緻優先隊列中的元素個數過多，時間複雜度和空間複雜度過高，是以需要使用優化的表示法。可以在優先隊列中存儲二進制組，每個二進制組表示蘋果的腐爛日期和在該日期腐爛的蘋果個數，則優先隊列中的元素個數最多為 n 個（即數組長度），可以顯著降低時間複雜度和空間複雜度。
計算吃蘋果的最大數目分成兩個階段，第一階段是第 0 天到第 n−1 天，即天數在數組下标範圍内，第二階段是第 n 天及以後，即天數在數組下标範圍外。
在第一階段，由于每天樹上都可能長出蘋果，是以需要對每一天分别計算是否能吃到蘋果，并更新優先隊列。具體做法如下：
1. 将優先隊列中的所有腐爛日期小于等于目前日期的元素取出，這些元素表示已經腐爛的蘋果，無法食用；
2. 根據 days 和 apples 的目前元素計算當天長出的蘋果的腐爛日期和數量，如果數量大于 0，則将腐爛日期和數量加入優先隊列；
3. 如果優先隊列不為空，則當天可以吃 1 個蘋果，将優先隊列的隊首元素的數量減 1，如果隊首元素的數量變成 0 則将隊首元素取出。
在第二階段，由于樹上不會再長出蘋果，是以隻需要考慮能吃到的蘋果數量。由于優先隊列中的每個元素的數量可能很大，是以需要根據目前日期和優先隊列的隊首元素的腐爛日期和數量計算能吃到的蘋果數量。
假設目前日期是第 i 天，首先将優先隊列中的所有腐爛日期小于等于 i 的元素取出，如果優先隊列不為空，則根據優先隊列的隊首元素計算能吃到的蘋果數量。假設優先隊列的隊首元素的腐爛日期是 x，數量是 y，其中 x>i，則有 y 個蘋果，距離腐爛還有 x−i 天，是以能吃到的蘋果數量是 curr=min(x − i,y)。将優先隊列的隊首元素 (x,y) 取出并将日期增加 curr，重複上述操作直到優先隊列為空，即可得到吃蘋果的最大數目。
代碼
Python3
class Solution:
def eatenApples(self, apples: List[int], days: List[int]) -> int:
ans = 0
pq = []
i = 0
while i < len(apples):
while pq and pq[0][0] <= i:
heappop(pq)
if apples[i]:
heappush(pq, [i + days[i], apples[i]])
if pq:
pq[0][1] -= 1
if pq[0][1] == 0:
heappop(pq)
ans += 1
i += 1
while pq:
while pq and pq[0][0] <= i:
heappop(pq)
if len(pq) == 0:
break
p = heappop(pq)
num = min(p[0] - i, p[1])
ans += num
i += num
return ans C++
typedef pair<int,int> pii;
class Solution {
public:
int eatenApples(vector<int>& apples, vector<int>& days) {
int ans = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
int n = apples.size();
int i = 0;
while (i < n) {
while (!pq.empty() && pq.top().first <= i) {
pq.pop();
}
int rottenDay = i + days[i];
int count = apples[i];
if (count > 0) {
pq.emplace(rottenDay, count);
}
if (!pq.empty()) {
pii curr = pq.top();
pq.pop();
curr.second--;
if (curr.second != 0) {
pq.emplace(curr.first, curr.second);
}
ans++;
}
i++;
}
while (!pq.empty()) {
while (!pq.empty() && pq.top().first <= i) {
pq.pop();
}
if (pq.empty()) {
break;
}
pii curr = pq.top();
pq.pop();
int num = min(curr.first - i, curr.second);
ans += num;
i += num;
}
return ans;
}
}; Java
class Solution {
public int eatenApples(int[] apples, int[] days) {
int ans = 0;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
int n = apples.length;
int i = 0;
while (i < n) {
while (!pq.isEmpty() && pq.peek()[0] <= i) {
pq.poll();
}
int rottenDay = i + days[i];
int count = apples[i];
if (count > 0) {
pq.offer(new int[]{rottenDay, count});
}
if (!pq.isEmpty()) {
int[] arr = pq.peek();
arr[1]--;
if (arr[1] == 0) {
pq.poll();
}
ans++;
}
i++;
}
while (!pq.isEmpty()) {
while (!pq.isEmpty() && pq.peek()[0] <= i) {
pq.poll();
}
if (pq.isEmpty()) {
break;
}
int[] arr = pq.poll();
int curr = Math.min(arr[0] - i, arr[1]);
ans += curr;
i += curr;
}
return ans;
}
} Golang
func eatenApples(apples, days []int) (ans int) {
h := hp{}
i := 0
for ; i < len(apples); i++ {
for len(h) > 0 && h[0].end <= i {
heap.Pop(&h)
}
if apples[i] > 0 {
heap.Push(&h, pair{i + days[i], apples[i]})
}
if len(h) > 0 {
h[0].left--
if h[0].left == 0 {
heap.Pop(&h)
}
ans++
}
}
for len(h) > 0 {
for len(h) > 0 && h[0].end <= i {
heap.Pop(&h)
}
if len(h) == 0 {
break
}
p := heap.Pop(&h).(pair)
num := min(p.end-i, p.left)
ans += num
i += num
}
return
}
type pair struct{ end, left int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].end < h[j].end }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func min(a, b int) int {
if a > b {
return b
}
return a
} 複雜度分析
- 時間複雜度：O(n log n)，其中 n 是數組 apples 和 days 的長度。優先隊列中最多有 n 個元素，每個元素加入優先隊列和從優先隊列中取出各一次，每次操作的時間複雜度是 O(log n)，是以總時間複雜度是 O(n logn)。
- 空間複雜度：O(n)，其中 n 是數組 apples 和 days 的長度。空間複雜度主要取決于優先隊列，優先隊列中的元素個數不會超過 n。
本文作者：力扣
聲明：本文歸“力扣”版權所有，如需轉載請聯系。
![LeetCode 雙周賽 107（2023/06/24）滑動視窗與離散化[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)