leetcode1405. 最长快乐字符串(mid)

解题思路

代码
力扣链接

大佬题解

贪心+优先队列 代码

class Solution {
    public String longestDiverseString(int a, int b, int c) {

        //根据字符个数降序排列
        //arr[0]: (0,1,2) -> ('a','b','c'),arr[1]: 字符对应个数
        PriorityQueue pq = new PriorityQueue<>((x, y) -> y[1] - x[1]);
        if (a > 0) {
            pq.add(new int[]{0, a});
        }
        if (b > 0) {
            pq.add(new int[]{1, b});
        }
        if (c > 0) {
            pq.add(new int[]{2, c});
        }

        StringBuilder builder = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            //当前字符串的长度,如果大于2需要检查末尾是否存在两个字符和当前字符相等
            int n = builder.length();
            char ch = (char) (first[0] + 'a');
            if (n >= 2 && ch == builder.charAt(n - 1) && ch == builder.charAt(n - 2)) {
                //队列为空,直接终止
                if (pq.isEmpty()) {
                    break;
                }
                int[] second = pq.poll();
                ch = (char) (second[0] + 'a');
                builder.append(ch);
                //如果次大字符可用次数-1仍大于0，将其添加回优先队列
                if (--second[1] > 0) {
                    pq.offer(second);
                }
                //将最大字及其可用次数重新添加到队列
                pq.offer(first);
            } else {
                builder.append(ch);
                if (--first[1] > 0) {
                    pq.offer(first);
                }
            }
        }
        return builder.toString();
    }
}