文章目錄
- 題目
- 題目決議
- 解題方法 ： 貪心思想 + 優先佇列
- 來跟著我一步步看,怎么實作這個代碼
- 第一步： 創建 三個變數 和 new 一個 PriorityQueue（優先佇列），并制定該佇列，每次取出 "蘋果 / 資料" 時，永遠是快要壞掉的 "蘋果 / 資料"，
- 第二步開始遍歷 apples 和 days 陣列，確認每天產出蘋果數量 和 該天產出蘋果的保質期，如果到了保質日期，就丟掉，如果沒過保質期，就代表我們需要記入 今天蘋果的個數和保質期（前提今天有蘋果產出），而且也意味著我們今天開始可以吃一個蘋果，但是這個蘋果一定某天產出的蘋果（該天產出蘋果保質期是最短的），當我們吃完該天的蘋果（前提是沒過期），我們就可以將其存盤的資訊洗掉掉了，
- 第三步： 計算帶回家的蘋果還可以吃幾天
- 最后附上程式
題目
?
題目決議
題目的意思，我給你們大概整理了一下：一個蘋果樹，每天 產出 count 個蘋果（有可能不產出，即 count == 0），現在的情況呢，就是我們嘴饞，看到老家有顆蘋果樹，幾乎每天都可能產出蘋果，這不吃，對得起我們這張嘴嗎？對不起，知道嘛！所以我們在老家待的 i 天里，每天都要吃一個蘋果，臨走的時候還要順著幾個，當然肯定是當天沒壞的，而且按照家里人的習慣，會把待在家里這幾天沒壞的新鮮水果全部給你，
我們呢，為了不浪費，每天吃的都是過幾天就可能壞的蘋果，但是呢！一個人的力量是有限的，
我們每天只吃一個蘋果，吃完這個蘋果，我們不再吃了，意味著：其他蘋果，今天失去了被吃的機會！同時保質日期減一，
再加上家里人，認為自己家種的蘋果就跟不要錢一樣，往死里塞，完全不管人家受不受得了！
也就是說：存在 部分蘋果 會腐爛，那就只能丟了，
大概就是這么個情況，
?
解題方法 ： 貪心思想 + 優先佇列
貪心思想，其實在題目決議的時候就講了，為了吃得更多，我們選擇吃那些再不吃過幾天就會壞掉的蘋果，而優先佇列 是為了我們讓我們每次吃得蘋果剛好就是我們想吃的那種蘋果，這就相當于 優先佇列，即使幫我們分好蘋果，快壞的蘋果永遠在我們面前，
?
來跟著我一步步看,怎么實作這個代碼
第一步： 創建 三個變數 和 new 一個 PriorityQueue（優先佇列），并制定該佇列，每次取出 “蘋果 / 資料” 時，永遠是快要壞掉的 “蘋果 / 資料”，
?
第二步開始遍歷 apples 和 days 陣列，確認每天產出蘋果數量 和 該天產出蘋果的保質期，如果到了保質日期，就丟掉，如果沒過保質期，就代表我們需要記入 今天蘋果的個數和保質期（前提今天有蘋果產出），而且也意味著我們今天開始可以吃一個蘋果，但是這個蘋果一定某天產出的蘋果（該天產出蘋果保質期是最短的），當我們吃完該天的蘋果（前提是沒過期），我們就可以將其存盤的資訊洗掉掉了，
?
第三步： 計算帶回家的蘋果還可以吃幾天
?
最后附上程式
class Solution {
public int eatenApples(int[] apples, int[] days) {
int result = 0; // 最終結果 - 最多吃幾個蘋果
int n = apples.length;// 獲取在老家待多少天，
int i = 0;// 記錄天數，用來對比保質期
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);// 每次取出的資料,都是保質期最短的那一組
while(i<n){
while(!pq.isEmpty() && pq.peek()[0] <= i){//檢查 今天是否有某一天的蘋果腐爛了（到保質期了），
// pq.peek() 是回傳佇列中的頭元素，因為我們是優先佇列，所以 最快壞掉的蘋果，就放在頭位置
pq.poll();// 到期了，就扔掉，由此我們知道 poll 就洗掉出佇列元素的方法
}
int rottenDay = i + days[i];// 記錄當天產出蘋果的保質期
int count = apples[i];// 記錄 當天產出的蘋果數量
if(count > 0){// 只有產出蘋果，才有被記錄資訊的價值
pq.offer(new int[]{rottenDay,count});// 你現在可以看看 while(i<n)后面 while回圈的條條件為什么是讓 佇列的頭元素，來比較，
}
if(!pq.isEmpty()){// 這個if陳述句是為了防止 某天沒有產出蘋果，剛好又沒有存貨，
int[] arr = pq.peek();//獲取 佇列頭元素,或者說：獲取某天產出蘋果（保質期最短的）資訊
arr[1]--;// 每天吃的那一個蘋果，
if(arr[1]==0){// 把某天快壞的蘋果吃完了
pq.poll();// 那就沒必要記著該天的蘋果資訊
}
result++;// 我們此時吃到了一個蘋果
}
i++;// 過去了一天
}
// 回去的那天，帶回來的蘋果
while(!pq.isEmpty()){//防止這幾天產出的蘋果，剛好夠吃，所以佇列中也就沒有資料（沒有蘋果可以帶走）
while(!pq.isEmpty() && pq.peek()[0]<=i){
// 這個跟上面的那個 while回圈是一樣的，檢查有沒有那天的蘋果到了日期，
pq.poll();//到期， 丟掉，
}
if(pq.isEmpty()){// 昨天帶回來的蘋果，今天就全爛了,丟完了，佇列中自然就是空的，沒有資料
break;// 那就沒必要進行下一步，直接終止回圈，回傳 最終結果 result，
}
//如果程式走到這里，說明不滿足回圈 和 if 條件，
// 意味著：有口福了，今天還有蘋果可以吃
int[] arr = pq.poll();// 獲取某天最快壞掉的蘋果資訊（保質期，和個數）
int eatDay = Math.min(arr[0]- i,arr[1] );//
// 首先，我們肯定只會吃沒腐爛的蘋果,其次我們每天只吃一個，
// 保質期減去今天，不就是蘋果還有幾天過期？ 又可以說 一天吃一個蘋果可以吃幾天，
// 但是可能存在 吃不完蘋果，導致腐爛的情況，或者說 在蘋果壞掉之前，剛好吃完，
// 所以我們要選取最小值，來保證每天遲到蘋果不是壞的，
// 我們吃的 蘋果數量 和 天數 同時 加上 eatDay， （一天一個蘋果）
result += eatDay;
i += eatDay;
}
return result;// 回傳我們最終吃進肚子里的蘋果總數
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/392096.html
標籤：java