堆——java中优先队列（下）

堆

984. 不含 AAA 或 BBB 的字符串

class Solution {
    public String strWithout3a3b(int a, int b) {
        StringBuffer  str=new StringBuffer();
        while(a>0&&b>0){
            if(a>b){
                str.append("aab");
                a-=2;
                b--;
            }else if(a==b){
                str.append("ab");
                a--;b--;
            }else if(a<b){
                str.append("bba");
                a--;b-=2;
            }
        }
        while(a > 0) {
            str.append('a');
            a--;
        }
        while(b> 0) {
            str.append('b');
            b--;
        }
        return str.toString();
    }
}

767. 重构字符串

class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) {
            count.merge(c, 1, Integer::sum);
        }
        List<Map.Entry<Character, Integer>> a = new ArrayList<>(count.entrySet());
        a.sort((p, q) -> q.getValue() - p.getValue());
        int m = a.get(0).getValue();
        if (m > n - m + 1) {//最大字符出现的次数大于其它字符的n+1个数返回为null
            return "";
        }
        char[] ans = new char[n];
        int i = 0;
        for (Map.Entry<Character, Integer> entry : a) {
            char ch = entry.getKey();
            int cnt = entry.getValue();
            while (cnt-- > 0) {
                ans[i] = ch;
                i += 2;
                if (i >= n) {
                    i = 1;
                }
            }
        }
        return new String(ans);
    }
}

1953. 你可以工作的最大周数

class Solution {
    public long numberOfWeeks(int[] milestones) {
        long s = 0;
        int m = 0;
        for (int x : milestones) {
            s += x;
            m = Math.max(m, x);
        }
        return m > s - m + 1 ? (s - m) * 2 + 1 : s;
    }
}

373. 查找和最小的 K 对数字

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> sum = new ArrayList<>(k);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            pq.add(new int[]{nums1[i] + nums2[0], i, 0});
        }
        while (sum.size() < k) {
            int[] p = pq.poll();
            int i = p[1];
            int j = p[2];
            sum.add(List.of(nums1[i], nums2[j]));
            if (j + 1 < nums2.length) {
                pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
            }
        }
        return sum;
    }
}

后悔堆

"后悔堆"是一种数据结构，它在处理贪心算法问题时，允许我们在做出贪心选择后，如果发现结果不是最优的，可以"反悔"并重新做出选择。这种数据结构的核心思想是，通过维护一个候选解的集合，当当前的选择不是最优解时，可以从这个集合中重新选择一个更好的解。

LCP 30. 魔塔游戏

class Solution {
    public int magicTower(int[] nums) {
        long sum=0;
        for(int s:nums)sum+=s;
        if(sum<0)return -1;
        int num=0;
        long hp=1;
        PriorityQueue<Integer> p= new PriorityQueue<>();
        for (int t:nums) {
        if(t<0)p.offer(t);
         hp+=t;
         if (hp < 1) {
                hp -= p.poll();
                num++;
            }
        }
        return num;
    }
}

1642. 可以到达的最远建筑

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        Queue<Integer> queue = new PriorityQueue<>();
        int sum=0;
        for(int i = 1; i < heights.length; i++) {
            int diff= heights[i] - heights[i - 1];
            if(diff>0) {
                queue.offer(diff);
                if(queue.size() > ladders) {
                    sum += queue.poll();
                }
                if(sum > bricks)
                    return i - 1;
            }
        }
        return heights.length-1;
    }
}

懒删除堆

在懒删除堆中，当一个元素被删除时，它不会被立即从堆中移除，而是被标记为已删除。只有当这个元素在后续的操作中被实际需要时，它才会被彻底移除。这种策略可以减少不必要的操作，因为不是所有的删除请求都需要立即执行。例如，如果一个元素被标记为删除，但在之后的某个时刻又需要被重新插入，那么实际上就不需要进行删除操作。

3092. 最高频率的 ID

class Solution {
    public long[] mostFrequentIDs(int[] nums, int[] freq) {
        int n = nums.length;
        long[] ans = new long[n];
        Map<Integer, Long> cnt = new HashMap<>();
        PriorityQueue<Pair<Long, Integer>> pq = new PriorityQueue<>((a, b) -> Long.compare(b.getKey(), a.getKey()));
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            long c = cnt.merge(x, (long) freq[i], Long::sum);
            pq.add(new Pair<>(c, x));
            while (!pq.peek().getKey().equals(cnt.get(pq.peek().getValue()))) { 
                pq.poll();
            }
            ans[i] = pq.peek().getKey();
        }
        return ans;
    }
}

对顶堆

在Java中，“对顶堆”（Dual-Pivot Heap）是一种特殊类型的堆数据结构，它结合了最大堆和最小堆的特点。对顶堆是一种二叉堆，它在堆的顶部同时维护两个指针，分别指向最大元素和最小元素。这种设计允许对顶堆在对数时间内高效地执行最大元素的查找、最小元素的查找、最大元素的删除和最小元素的删除。

LCP 24. 数字游戏

class Solution {
    public int[] numsGame(int[] nums) {
        final int MOD = 1_000_000_007;
        int[] ans = new int[nums.length];
        PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a); // 维护较小的一半，大根堆
        PriorityQueue<Integer> right = new PriorityQueue<>(); // 维护较大的一半，小根堆
        long leftSum = 0, rightSum = 0;
        for (int i = 0; i < nums.length; i++) {
            int b = nums[i] - i;
            if (i % 2 == 0) { // 前缀长度是奇数
                if (!left.isEmpty() && b < left.peek()) {
                    leftSum -= left.peek() - b;
                    left.offer(b);
                    b = left.poll();
                }
                rightSum += b;
                right.offer(b);
                ans[i] = (int) ((rightSum - right.peek() - leftSum) % MOD);
            } else { // 前缀长度是偶数
                if (b > right.peek()) {
                    rightSum += b - right.peek();
                    right.offer(b);
                    b = right.poll();
                }
                leftSum += b;
                left.offer(b);
                ans[i] = (int) ((rightSum - leftSum) % MOD);
            }
        }
        return ans;
    }
}