算法：优先队列，贪心

容易想到用优先队列，但是难点在于【动态地】去消耗和维护优先队列里的元素；

关键点在于想到用一个临时数组来存从堆中弹出的元素（动态消耗），再推进堆中（动态维护）。

统计答案的关键：每次消耗元素（除了最后一组），必定耗费n+1个时间片，所以要尽可能多地消耗元素（贪心）；另外需要特判最后一组消耗的时间

时间复杂度

$O(N)$, 堆中的元素个数为常数个

代码

class Solution {
public:

    // 难点：用合适的算法/数据结构去动态维护TopN元素的想法
    // 关键点：用优先队列，每次弹出TopN个，消耗后再压入优先队列
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> cnt(26);
        for(auto i: tasks){
            cnt[i-'A'] ++;
        }

        priority_queue<int> q;
        for(int i = 0; i < 26; i ++){
            if(cnt[i] > 0) q.push(cnt[i]);
        }

        int ans = 0;
        while(1){
            vector<int> tmp;

            /* 关键：动态维护TopN元素 */
            for(int i = 1; i <= n + 1; i ++){
                if(q.size()){
                    tmp.push_back(q.top()-1);
                    q.pop();
                }else{
                    break;
                }
            }
            for(int t: tmp){
                if(t > 0) q.push(t);
            }

            /* 统计答案 */
            if(q.size()){
                ans += n+1;
            }else{ // 最后一组
                ans += tmp.size();
                break;
            }

        }
        return ans;
    }
};

扩展

前K个高频元素同样是求TopN的一道题，但是只用求一次，没有这道题所要求的动态性，就可以用“频次的频次数组”来替代优先队列，优化复杂度