Daily LeetCode – day0010 0761. Special Binary String

// 0761. Special Binary String
class Solution {
    public String makeLargestSpecial(String s) {
        if (s.length() < 3) {
            return s;
        }
        int prefixSum = 0;
        int processed = 0;
        PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '1') {
                ++prefixSum;
            } else {
                --prefixSum;
                if (prefixSum == 0) {
                    pq.offer("1" + makeLargestSpecial(s.substring(processed + 1, i)) + "0");
                    processed = i + 1;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            sb.append(pq.poll());
        }
        return sb.toString();
    }
}

学习笔记：
这是一道很困难的字符串题，需要用到分治思想递归调用。
找到每一个最大的1和0包的部分，再内部排序，排完序之后整体排序。
看完后会发觉这道题目的精妙。
一开始我用了List和Collections.sort()，String.join()来返回，这样时间是3ms。
我觉得可能是排序消耗比较花时间吧，就改用了PriorityQueue，用了之后就报错了，这里有一个坑，就是使用 增强for循环 和 迭代器遍历 是不可以按正确顺序遍历PriorityQueue的，所以得用记录size后的普通for循环 或者 while循环来遍历。
这道题的PriorityQueue是个最大堆，可以使用Comparator，也可以使用lambda表达式。
(o1, o2) -> {return o2.compareTo(o1);}