1705. 吃蘋果的最大數目

思路

貪心的去想，每次吃的蘋果都選擇最接近過期的那一顆。
由於需要不斷的尋找極值，且每天可能會有新的蘋果加入，
因此用優先隊列，來快速得到要吃的蘋果。

在沒有蘋果可以吃時就結束，除非未來還有可能會有新的蘋果。

程式碼

優先隊列

class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        using pii = pair<int, int>;
        int n = apples.size();
        priority_queue<pii, vector<pii>, greater<pii>> pq; // 紀錄蘋果的過期時間跟個數
        int i = 0; // 當前天數
        int res = 0;
        while(i < n || !pq.empty()) { // 還沒遍歷完 || 還有蘋果可以吃
            // 1. 當天的蘋果加入
            if(i < n && apples[i] > 0) {
                pq.push({i + days[i], apples[i]});
            }
            // 2. 移除過期蘋果
            while(!pq.empty() && pq.top().first <= i) {
                pq.pop();
            }
            // 3. 吃蘋果
            if(!pq.empty()) {
                auto [expire, cnt] = pq.top();
                pq.pop();
                res++;
                if(cnt > 1) {
                    pq.push({expire, cnt - 1});
                }
            }
            i++;
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$