面试必问：Top K问题进阶

之前我们已经聊过了Top K问题的本质以及解题思路的切入点，虽然我们面试不会遇到原题，总会有这样那样的限制条件或者变形，让题目变复杂变难。没关系，我们已经掌握了问题的核心，剩下的只要针对特定的限制或条件做相应的处理，我们总可以把未知的问题转换成我们熟悉的形式。

至于看破问题本质跟把问题转换成我们熟悉的最简单的形式，这个看得多了自然就有感觉了。今天我们就来看一看Top K问题比较难的几个典型题目，加深对Top K问题套路的理解。

首先是这样的，给定一个字符串，看看它的字符能否重组使得相邻两个字符不一样。

示例1:

输入: "aappp"
输出: "papap"
解释: 在"papap", 不存在相邻的字符相同。

示例2:

输入: "Programming"
输出: "rgmrgmPiano"或"gmringmrPoa" 或"gmrPagimnor"等等
解释: 这么排相邻的字符不会重复。

示例3:

输入: "aapa"
输出: ""
解释: 随便怎么排，至少两个a靠在一起。

这个问题依旧很简短，但是却不能再一下子想出答案来了。用什么方法来解乍一看不是那么明朗，我们得好好观察一下示例来分析分析了。

要想让这些字符相邻的都不同，最关键的是要处理好出现频率最多的那个字符，把它们处理好了其它的出现频率少的字符放哪儿都可以。这就涉及到选出出现频率最高的那个字符了，并且插入一个字符后那个字符的出现频率就会-1，出现频率最高的字符可能还是这个字符，也可能不是这个字符，每一步我们都要找到出现频率最高的字符并优先处理。那题目也就转化成按出现频率顺序处理字符。这题目跟前面浅谈Top K问题文章第二题很类似了，这果然是一个Top K问题！那这个可以通过一个最大堆来解决。然后这里还是用一个贪心的策略，一步一步优先安排频率最高的字符加到结果字符串上，这样我们会最大概率让相邻俩字符不等。

所以，在每一步，我们要把出现频率最高的那个字符，附加到结果字符串上，然后不把它放回堆里去确保下一次取出来的不会是相同的字符，然后在下一步，我们会拿出下一个出现频率最高的字符附加到字符串上，然后把上一个字符放回堆里面，把它的频率-1，再拿出下一个频率最高的字符，以此类推。

如果以这样的方式我们拼接出了一个等长的字符串，那就算我们找到了符合条件的重组形式。

题目转换成了我们熟悉的形式，接下来实现的过程就轻松多了：

 public static String rearrangeString(String str) {
        Map<Character, Integer> charFrequencyMap = new HashMap<>();
        for (char chr : str.toCharArray())
            charFrequencyMap.put(chr, charFrequencyMap.getOrDefault(chr, 0) + 1);

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<Map.Entry<Character, Integer>>(
                (e1, e2) -> e2.getValue() - e1.getValue());

        //把最有字符加到最大堆
        maxHeap.addAll(charFrequencyMap.entrySet());

        Map.Entry<Character, Integer> previousEntry = null;
        StringBuilder resultString = new StringBuilder(str.length());
        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> currentEntry = maxHeap.poll();
            // 如果之前的字符出现次数还大于1，放回堆中
            if (previousEntry != null && previousEntry.getValue() > 0)
                maxHeap.offer(previousEntry);
            //把字符附加到结果字符串中
            resultString.append(currentEntry.getKey());
            currentEntry.setValue(currentEntry.getValue() - 1);
            previousEntry = currentEntry;
        }

        //如果最终结果跟输入字符串等长，代表我们找到了它
        return resultString.length() == str.length() ? resultString.toString() : "";
    }

经过了我们的一通分析，答案跃然纸上。现在再来看这道题，似乎就没那么难了。

我们的时间复杂度为 O(N*logN)O(N∗logN)，空间复杂度为O(N)。

有了这个经验以后，我们再来看另一道题，这次应该会轻松许多：给定一个数组表示 CPU 需要执行的任务列表，任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。然而，两个相同种类的任务之间必须有长度为K的冷却时间，因此至少有连续 K个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的最短时间。

示例1:

输入: [a, a, a, b, c, c], K=2
输出: 7
解释: a -> c -> b -> a -> c -> 待命 -> a

示例2:

输入: [a, b, a], K=3
输出: 5
解释: a -> b -> 待命 -> 待命 -> a

题目看起来还挺长，我们需要重组任务，让相同的任务相隔K个时间间隔再执行。那我们其实还是要让出现频率最多的任务优先执行，因为他们要被执行的次数比较多，每个任务被执行一次之后，它的次数可能还是最多，也可能不是，那我们也是要在每一步确定当前要被执行次数最多的任务。那这道题还是转化成了我们熟悉的Top K问题。

我们还是采用一个类似的方式，采用一个最大堆去优先执行出现频率最高的任务。执行完之后，我们减少它的频率，把它放到一个等待列表里，每一次循环都尽可能地执行K+1个任务，因为执行完K+1个任务之后，最开始的那个任务又可以继续执行了。这时我们把等待列表里面的任务放回到最大堆里面去，如果某次循环没有执行够K+1个任务，那剩下的时间里我们就要待命等到下一次循环。

这题目看起来老长老长的很难，仔细分析下来还是我们熟悉的味道，只不过是加了一些条件加了一些伪装，实现起来还是很简单的：

 public static int scheduleTasks(char[] tasks, int k) {
        int intervalCount = 0;
        Map<Character, Integer> taskFrequencyMap = new HashMap<>();
        for (char chr : tasks)
            taskFrequencyMap.put(chr, taskFrequencyMap.getOrDefault(chr, 0) + 1);

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<Map.Entry<Character, Integer>>(
                (e1, e2) -> e2.getValue() - e1.getValue());

        //把所有任务添加到堆中
        maxHeap.addAll(taskFrequencyMap.entrySet());

        while (!maxHeap.isEmpty()) {
            List<Map.Entry<Character, Integer>> waitList = new ArrayList<>();
            int n = k + 1; // 尝试执行K+1个任务
            for (; n > 0 && !maxHeap.isEmpty(); n--) {
                intervalCount++;
                Map.Entry<Character, Integer> currentEntry = maxHeap.poll();
                if (currentEntry.getValue() > 1) {
                    currentEntry.setValue(currentEntry.getValue() - 1);
                    waitList.add(currentEntry);
                }
            }
            maxHeap.addAll(waitList); // 把等待列表里的任务放回堆中
            if (!maxHeap.isEmpty())
                intervalCount += n; // 加上我们需要待命的次数
        }

        return intervalCount;
    }

在这里因为我们每次都要从堆中移除一个任务，最终处理所有任务，所以时间复杂度是O(N*logN)，而最坏的情况下我们要存储所有的任务在哈希表里面，空间复杂度是 O(logN)。

怎么样，有木有一种灵光一闪的感觉？其实Top K问题就是这么回事儿，它的套路就是这样，我们需要看透问题的本质，追本溯源，只要能敏锐地抓住问题中表露给我们的信息，那就很容易转化成我们熟悉的题目，就能用我们熟悉的套路，就算有特别的限制条件那也无非是在我们的套路之上做对应的处理。

好了，就到这里了，希望我的这些分析能加深大家的理解跟体会，为大家拿下Top K问题提供一些帮助。Happy coding~