進階堆積技巧

HEAP    = a bag of CANDIDATES   (some are stale / outdated)
HASHMAP = the SOURCE OF TRUTH   (current real value of each key)

# the whole pattern in 3 lines
c_map[key] = new_value                          # 1. update truth
heapq.heappush(pq, (-new_value, key))           # 2. push new candidate (old one stays!)
while pq and -pq[0][0] != c_map[pq[0][1]]:      # 3. pop stale tops until top is valid
    heapq.heappop(pq)

# python
# IDEA: heap holds stale candidates; hashmap holds truth; clean top lazily
import heapq

class LazyMaxTracker:
    def __init__(self):
        self.truth = {}   # key -> current real value  (SOURCE OF TRUTH)
        self.pq = []      # max-heap of (-value, key)  (CANDIDATES, may be stale)

    def update(self, key, delta):
        # 1. update the truth
        self.truth[key] = self.truth.get(key, 0) + delta
        # 2. push new candidate -- do NOT remove the old entry
        heapq.heappush(self.pq, (-self.truth[key], key))

    def top(self):
        # 3. lazy delete: pop stale tops ONLY until the top is valid
        while self.pq and -self.pq[0][0] != self.truth[self.pq[0][1]]:
            heapq.heappop(self.pq)
        return -self.pq[0][0] if self.pq else 0

// java
// IDEA: PriorityQueue of stale candidates + HashMap of truth
class LazyMaxTracker {
    Map<Integer, Long> truth = new HashMap<>();               // key -> real value
    // max-heap by value: long[]{value, key}
    PriorityQueue<long[]> pq =
        new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));

    public void update(int key, long delta) {
        long v = truth.getOrDefault(key, 0L) + delta;
        truth.put(key, v);
        pq.offer(new long[]{v, key});                          // old entry left behind
    }

    public long top() {
        // pop stale tops only until the top is valid, then stop
        while (!pq.isEmpty() && pq.peek()[0] != truth.get((int) pq.peek()[1])) {
            pq.poll();
        }
        return pq.isEmpty() ? 0 : pq.peek()[0];
    }
}

nums = [2,3,2,1],  freq = [3,2,-3,1]

step 0: c_map={2:3}          push(-3,2)   top=(-3,2) valid           -> ans 3
step 1: c_map={2:3,3:2}      push(-2,3)   top=(-3,2) valid           -> ans 3
step 2: c_map={2:0,3:2}      push( 0,2)   top=(-3,2) STALE (2 is 0)  -> pop
                                          top=(-2,3) valid -> STOP   -> ans 2
                                          ( (0,2) still sits in pq, untouched )
step 3: c_map={2:0,3:2,1:1}  push(-1,1)   top=(-2,3) valid           -> ans 2

output = [3,3,2,2]

# python
# LC 3092 - Most Frequent IDs
# IDEA: hashmap of true counts + max-heap of (-count, id) candidates; pop stale tops at read time
# time = O(n log n), space = O(n)
import heapq

def mostFrequentIDs(nums, freq):
    c_map = {}   # id -> TRUE frequency
    pq = []      # max-heap of (-frequency, id), possibly stale
    ans = []
    for val, cnt in zip(nums, freq):
        c_map[val] = c_map.get(val, 0) + cnt         # 1. update the truth
        heapq.heappush(pq, (-c_map[val], val))       # 2. push; the old entry stays behind
        while pq and -pq[0][0] != c_map[pq[0][1]]:   # 3. pop stale tops only
            heapq.heappop(pq)
        ans.append(-pq[0][0] if pq else 0)           # 4. the top is now accurate
    return ans

// java
// LC 3092 - Most Frequent IDs
// IDEA: HashMap of true counts + max-heap of {count, id} candidates; poll stale tops at read time
// time = O(n log n), space = O(n)
public long[] mostFrequentIDs(int[] nums, int[] freq) {
    Map<Integer, Long> cMap = new HashMap<>();          // id -> TRUE frequency
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
    int n = nums.length;
    long[] ans = new long[n];
    for (int i = 0; i < n; i++) {
        int val = nums[i];
        long cur = cMap.getOrDefault(val, 0L) + freq[i];
        cMap.put(val, cur);                              // 1. update the truth
        pq.offer(new long[]{cur, val});                  // 2. the old entry stays behind
        while (!pq.isEmpty() && pq.peek()[0] != cMap.get((int) pq.peek()[1])) {
            pq.poll();                                   // 3. drop stale tops only
        }
        ans[i] = pq.isEmpty() ? 0 : pq.peek()[0];        // 4. read the answer
    }
    return ans;
}

price_map[ts] = price      <- SOURCE OF TRUTH (one per timestamp, overwritten on correction)
max_heap: (-price, ts)     <- CANDIDATES for maximum()
min_heap: ( price, ts)     <- CANDIDATES for minimum()

an entry is STALE  iff  its price != price_map[its ts]

# python
# LC 2034 - Stock Price Fluctuation
# IDEA: one hashmap of truth + two mirrored lazy heaps; clean both tops inside update()
# time = update O(log n) amortised, current/maximum/minimum O(1), space = O(n)
import heapq

class StockPrice(object):
    def __init__(self):
        self.price_map = {}    # timestamp -> CURRENT price   (SOURCE OF TRUTH)
        self.max_time = 0      # biggest timestamp seen  -> current() is O(1)
        self.max_heap = []     # (-price, timestamp)     (CANDIDATES, may be stale)
        self.min_heap = []     # ( price, timestamp)

    def update(self, timestamp, price):
        # 1. overwrite the truth -- this is what makes old heap entries stale
        self.price_map[timestamp] = price
        self.max_time = max(self.max_time, timestamp)

        # 2. push into BOTH heaps; never remove the old entries
        heapq.heappush(self.max_heap, (-price, timestamp))
        heapq.heappush(self.min_heap, (price, timestamp))

        # 3. clean both tops: pop only while the top disagrees with price_map.
        #    No emptiness guard: the entry just pushed is valid, so neither heap can empty.
        while -self.max_heap[0][0] != self.price_map[self.max_heap[0][1]]:
            heapq.heappop(self.max_heap)
        while self.min_heap[0][0] != self.price_map[self.min_heap[0][1]]:
            heapq.heappop(self.min_heap)

    def current(self):
        return self.price_map[self.max_time]

    def maximum(self):
        return -self.max_heap[0][0]   # top is clean -> O(1)

    def minimum(self):
        return self.min_heap[0][0]

// java
// LC 2034 - Stock Price Fluctuation
// IDEA: HashMap of truth + two mirrored lazy heaps; both tops cleaned inside update()
// time = update O(log n) amortised, current/maximum/minimum O(1), space = O(n)
class StockPrice {
    private final Map<Integer, Integer> priceMap = new HashMap<>();   // ts -> CURRENT price
    private int maxTime = 0;
    // both heaps hold {price, timestamp}; only the ordering differs
    private final PriorityQueue<int[]> maxHeap =
        new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
    private final PriorityQueue<int[]> minHeap =
        new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

    public void update(int timestamp, int price) {
        priceMap.put(timestamp, price);
        maxTime = Math.max(maxTime, timestamp);
        maxHeap.offer(new int[]{price, timestamp});
        minHeap.offer(new int[]{price, timestamp});

        // clean BOTH tops; the entry just pushed is valid, so neither heap can empty
        while (maxHeap.peek()[0] != priceMap.get(maxHeap.peek()[1])) maxHeap.poll();
        while (minHeap.peek()[0] != priceMap.get(minHeap.peek()[1])) minHeap.poll();
    }

    public int current() { return priceMap.get(maxTime); }
    public int maximum() { return maxHeap.peek()[0]; }
    public int minimum() { return minHeap.peek()[0]; }
}

update(1,10)  price_map={1:10}        max_heap=[(-10,1)]                 max=10  min=10
update(2, 5)  price_map={1:10, 2:5}   max_heap=[(-10,1),(-5,2)]          max=10  min=5
update(1, 3)  price_map={1:3,  2:5}   top (-10,1): price_map[1]=3 != 10  -> STALE, pop
                                      top  (-5,2): price_map[2]=5 == 5   -> valid, STOP
                                      max_heap=[(-5,2),(-3,1)]           max=5   min=3
update(4, 2)  price_map={1:3,2:5,4:2} max_heap=[(-5,2),(-3,1),(-2,4)]    max=5   min=2

min_heap still holds the stale (10,1) from step 1 — it is below (2,4),(3,1),(5,2),
so nothing ever asks about it. That is the point: it is never paid for.

HEAP  = (value, endCoordinate)   sorted by value
ALIVE = heap entries with endCoordinate > sweepPosition

# python
# LC 218 - The Skyline Problem
# time = O(N log N), space = O(N)
# IDEA: sweep x; max-heap of (height, end); lazy-pop buildings whose end <= x; emit on height change
import heapq

class Solution(object):
    def getSkyline(self, buildings):
        # start event: (L, -H, R)   |   end event: (R, 0, 0)
        # sorting on (-H) puts starts before ends at the same x,
        # and taller starts before shorter starts
        events = [(L, -H, R) for L, R, H in buildings]
        events += list({(R, 0, 0) for _, R, _ in buildings})
        events.sort()

        res = [[0, 0]]                      # sentinel: ground level
        live = [(0, float('inf'))]          # max-heap of (-H, end); ground never expires

        for x, negH, R in events:
            # 1) LAZY EVICT: drop every alive entry that already ended
            while live[0][1] <= x:
                heapq.heappop(live)
            # 2) INSERT: only start events carry a height
            if negH:
                heapq.heappush(live, (negH, R))
            # 3) READ: top of heap = current skyline height
            if res[-1][1] != -live[0][0]:
                res.append([x, -live[0][0]])

        return res[1:]

// java
// LC 218 - The Skyline Problem
// time = O(N log N), space = O(N)
// IDEA: sweep x; max-heap of {height, end}; lazy-pop ended buildings; emit on height change
public List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2], b[1]});   // start: NEGATIVE height
        events.add(new int[]{b[1], 0, 0});          // end marker
    }
    // same x -> starts (neg) before ends (0); taller start first
    events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
                                       : Integer.compare(a[1], b[1]));

    // max-heap of {height, end}; ground sentinel never expires
    PriorityQueue<int[]> live = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
    live.offer(new int[]{0, Integer.MAX_VALUE});

    List<List<Integer>> res = new ArrayList<>();
    int prevH = 0;

    for (int[] e : events) {
        int x = e[0];
        // 1) LAZY EVICT  (size > 1 protects the sentinel: R can be 2^31 - 1 == Integer.MAX_VALUE)
        while (live.size() > 1 && live.peek()[1] <= x) live.poll();
        // 2) INSERT
        if (e[1] < 0) live.offer(new int[]{-e[1], e[2]});
        // 3) READ
        int curH = live.peek()[0];
        if (curH != prevH) {
            res.add(Arrays.asList(x, curH));
            prevH = curH;
        }
    }
    return res;
}

Optimistically give EVERY cost a free pass.
Keep a MIN-HEAP of the costs currently holding a pass, capped at size k.
When the heap overflows -> the SMALLEST pass-holder is evicted and paid from the budget.

# python
# LC 1642 - Furthest Building You Can Reach
# time = O(N log L), space = O(L)   (L = ladders)
# IDEA: give every climb a ladder; when > L ladders are in use, downgrade the SMALLEST to bricks
import heapq

class Solution(object):
    def furthestBuilding(self, heights, bricks, ladders):
        ladder_jumps = []   # min-heap of the climbs currently using a ladder

        for i in range(len(heights) - 1):
            d = heights[i + 1] - heights[i]
            if d <= 0:
                continue                       # going down / flat is free

            heapq.heappush(ladder_jumps, d)    # optimistically use a ladder

            if len(ladder_jumps) > ladders:
                # the smallest climb loses its ladder and is paid with bricks
                bricks -= heapq.heappop(ladder_jumps)
                if bricks < 0:
                    return i                   # stuck standing on building i

        return len(heights) - 1

// java
// LC 1642 - Furthest Building You Can Reach
// time = O(N log L), space = O(L)   (L = ladders)
// IDEA: min-heap of climbs holding a ladder, capped at L; evicted (smallest) climb costs bricks
public int furthestBuilding(int[] heights, int bricks, int ladders) {
    PriorityQueue<Integer> ladderJumps = new PriorityQueue<>();   // min-heap

    for (int i = 0; i + 1 < heights.length; i++) {
        int d = heights[i + 1] - heights[i];
        if (d <= 0) continue;

        ladderJumps.offer(d);

        if (ladderJumps.size() > ladders) {
            bricks -= ladderJumps.poll();       // smallest climb downgraded to bricks
            if (bricks < 0) return i;
        }
    }
    return heights.length - 1;
}

// java
// LC 871 - Minimum Number of Refueling Stops
// IDEA: drive as far as fuel allows, pushing every passed station's fuel into a MAX-heap
//       ("I could have stopped there"); when stuck, retroactively refuel at the biggest one
// time = O(n log n), space = O(n)
public int minRefuelStops(int target, int startFuel, int[][] stations) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    int fuel = startFuel, i = 0, stops = 0;

    while (fuel < target) {
        // every station within reach becomes a "regret option"
        while (i < stations.length && stations[i][0] <= fuel) {
            pq.offer(stations[i][1]);
            i++;
        }
        if (pq.isEmpty()) return -1;    // no option left -> unreachable
        fuel += pq.poll();              // retroactively take the biggest tank
        stops++;
    }
    return stops;
}

# python
# LC 871 - Minimum Number of Refueling Stops
# IDEA: max-heap of fuel at already-passed stations; refuel from it only when stuck
# time = O(n log n), space = O(n)
import heapq

def minRefuelStops(target, startFuel, stations):
    pq = []                              # max-heap via negation
    fuel, i, stops = startFuel, 0, 0

    while fuel < target:
        while i < len(stations) and stations[i][0] <= fuel:
            heapq.heappush(pq, -stations[i][1])
            i += 1
        if not pq:
            return -1
        fuel -= heapq.heappop(pq)        # -(-max) => add the largest tank
        stops += 1

    return stops

# python
# LC 871 - Minimum Number of Refueling Stops (DP)
# IDEA: reach[t] = farthest position with exactly t stops; relax t backwards so each station is used once
# time = O(n^2), space = O(n)
def minRefuelStops_dp(target, startFuel, stations):
    n = len(stations)
    reach = [startFuel] + [0] * n   # reach[t] = farthest position with exactly t stops
    for i, (pos, fuel) in enumerate(stations):
        for t in range(i, -1, -1):  # backwards: station i is used at most once
            if reach[t] >= pos:
                reach[t + 1] = max(reach[t + 1], reach[t] + fuel)
    for t in range(n + 1):
        if reach[t] >= target:
            return t
    return -1

// java
// LC 630 - Course Schedule III
// IDEA: sort by deadline; greedily take each course, and if the schedule overflows,
//       regret the longest course already taken (max-heap of durations)
// time = O(n log n), space = O(n)
public int scheduleCourse(int[][] courses) {
    Arrays.sort(courses, (a, b) -> Integer.compare(a[1], b[1]));   // by deadline
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    int time = 0;

    for (int[] c : courses) {
        time += c[0];
        pq.offer(c[0]);
        if (time > c[1]) time -= pq.poll();   // undo the longest one taken
    }
    return pq.size();
}

# python
# LC 630 - Course Schedule III
# IDEA: sort by deadline; take every course, and regret the longest one when it overruns
# time = O(n log n), space = O(n)
import heapq

def scheduleCourse(courses):
    courses.sort(key=lambda x: x[1])   # sort by deadline
    heap = []   # max-heap (store negated durations)
    time = 0
    for duration, deadline in courses:
        if time + duration <= deadline:
            time += duration
            heapq.heappush(heap, -duration)
        elif heap and -heap[0] > duration:
            # Replace longest course with current shorter one
            time += duration + heap[0]   # heap[0] is negative
            heapq.heapreplace(heap, -duration)
    return len(heap)

# python
# LC 502 - IPO
# IDEA: unlock projects by capital, then greedily take the highest profit available
# time = O(n log n), space = O(n)
import heapq

def findMaximizedCapital(k, w, profits, capital):
    # Min-heap by capital (locked projects)
    locked = sorted(zip(capital, profits))
    # Max-heap by profit (available projects, negate for max-heap)
    available = []
    i = 0
    for _ in range(k):
        # Unlock all projects we can afford
        while i < len(locked) and locked[i][0] <= w:
            heapq.heappush(available, -locked[i][1])
            i += 1
        if not available: break
        w += -heapq.heappop(available)   # pick highest profit
    return w

freeHeap = min-heap by RESOURCE ID     -> "which resource do I hand out next?"
busyHeap = min-heap by RELEASE TIME    -> "which resource comes back first?"

1. RELEASE : while busyHeap and busyHeap.top.releaseTime <= now:  move it to freeHeap
2. ASSIGN  : take freeHeap.top   (or mint a brand-new resource if the pool is empty)
3. OCCUPY  : push (releaseTime, resourceId) into busyHeap

# python
# LC 1942 - The Number of the Smallest Unoccupied Chair
# time = O(N log N), space = O(N)
# IDEA: free chairs = min-heap by chair id; occupied = min-heap by leaving time; release -> assign
import heapq

class Solution(object):
    def smallestChair(self, times, targetFriend):
        # process friends in ARRIVAL order, but remember original index
        order = sorted(range(len(times)), key=lambda i: times[i][0])

        free = []          # min-heap of chair ids
        busy = []          # min-heap of (leave_time, chair_id)
        next_chair = 0

        for i in order:
            arrive, leave = times[i]

            # 1) RELEASE : chair frees exactly AT leave time -> `<=`
            while busy and busy[0][0] <= arrive:
                _, c = heapq.heappop(busy)
                heapq.heappush(free, c)

            # 2) ASSIGN : smallest free id, else mint a new chair
            if free:
                chair = heapq.heappop(free)
            else:
                chair = next_chair
                next_chair += 1

            if i == targetFriend:
                return chair

            # 3) OCCUPY
            heapq.heappush(busy, (leave, chair))

        return -1

// java
// LC 1942 - The Number of the Smallest Unoccupied Chair
// time = O(N log N), space = O(N)
// IDEA: free chairs = min-heap by id; busy chairs = min-heap by leaving time
public int smallestChair(int[][] times, int targetFriend) {
    int n = times.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(times[a][0], times[b][0]));   // by arrival

    PriorityQueue<Integer> free = new PriorityQueue<>();                    // chair ids
    PriorityQueue<int[]> busy = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // {leave, chair}
    int nextChair = 0;

    for (int i : order) {
        int arrive = times[i][0], leave = times[i][1];

        // 1) RELEASE
        while (!busy.isEmpty() && busy.peek()[0] <= arrive) {
            free.offer(busy.poll()[1]);
        }
        // 2) ASSIGN
        int chair = free.isEmpty() ? nextChair++ : free.poll();

        if (i == targetFriend) return chair;

        // 3) OCCUPY
        busy.offer(new int[]{leave, chair});
    }
    return -1;
}

// java
// LC 857 - Minimum Cost to Hire K Workers
// IDEA: pay ratio = wage/quality; sort workers by ratio ascending -> the current worker's
//       ratio is the ratio the whole group must be paid. Keep the k SMALLEST qualities
//       with a max-heap; answer = min(sumQuality * ratio).
// time = O(n log n), space = O(n)
public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
    int n = quality.length;
    double[][] workers = new double[n][2];             // [ratio, quality]
    for (int i = 0; i < n; i++) {
        workers[i] = new double[]{(double) wage[i] / quality[i], quality[i]};
    }
    Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));

    PriorityQueue<Double> pq = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    double sumQ = 0, res = Double.MAX_VALUE;

    for (double[] w : workers) {
        pq.offer(w[1]);
        sumQ += w[1];
        if (pq.size() > k) sumQ -= pq.poll();          // drop the largest quality
        if (pq.size() == k) res = Math.min(res, sumQ * w[0]);
    }
    return res;
}

# python
# LC 857 - Minimum Cost to Hire K Workers
# IDEA: sort by wage/quality ratio; max-heap keeps the k smallest qualities seen so far
# time = O(n log n), space = O(n)
import heapq

def mincostToHireWorkers(quality, wage, k):
    workers = sorted((w / q, q) for q, w in zip(quality, wage))
    pq, sum_q, res = [], 0, float('inf')

    for ratio, q in workers:
        heapq.heappush(pq, -q)          # max-heap via negation
        sum_q += q
        if len(pq) > k:
            sum_q += heapq.heappop(pq)  # pop returns -max -> adding it subtracts
        if len(pq) == k:
            res = min(res, sum_q * ratio)

    return res

# python
# LC 1383 - Maximum Performance of a Team
# IDEA: sort by efficiency descending; min-heap keeps the k fastest so far; current eff is the team min
# time = O(n log n), space = O(n)
import heapq

def maxPerformance(n, speed, efficiency, k):
    engineers = sorted(zip(efficiency, speed), reverse=True)   # efficiency high -> low
    heap = []          # min-heap of the speeds on the team
    speed_sum = 0
    best = 0
    for eff, spd in engineers:
        heapq.heappush(heap, spd)
        speed_sum += spd
        if len(heap) > k:
            speed_sum -= heapq.heappop(heap)   # drop the slowest
        best = max(best, speed_sum * eff)      # eff is the team minimum
    return best % (10**9 + 7)

// java
// LC 1383 - Maximum Performance of a Team
// IDEA: sort by efficiency descending; min-heap keeps the k fastest so far; current eff is the team min
// time = O(n log n), space = O(n)
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
    int[][] engineers = new int[n][2];                   // {efficiency, speed}
    for (int i = 0; i < n; i++) {
        engineers[i] = new int[]{efficiency[i], speed[i]};
    }
    Arrays.sort(engineers, (a, b) -> Integer.compare(b[0], a[0]));   // efficiency high -> low
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();          // speeds on the team
    long speedSum = 0;
    long best = 0;
    for (int[] eng : engineers) {
        minHeap.offer(eng[1]);
        speedSum += eng[1];
        if (minHeap.size() > k) {
            speedSum -= minHeap.poll();                  // drop the slowest
        }
        best = Math.max(best, speedSum * eng[0]);        // eng[0] is the team minimum
    }
    return (int) (best % 1_000_000_007);
}

speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
sorted by efficiency desc: (9,1) (7,5) (5,2) (4,10) (3,3) (2,8)

(9,1)   heap=[1]      sum=1    perf= 9
(7,5)   heap=[1,5]    sum=6    perf=42
(5,2)   heap=[2,5]    sum=7    perf=35   (1 dropped)
(4,10)  heap=[5,10]   sum=15   perf=60   <- answer

// java
// LC 407 - Trapping Rain Water II
// IDEA: water level is decided by the lowest wall on the border. Seed a min-heap with the
//       whole border, always expand the lowest cell; an inner neighbour lower than the
//       current level traps (level - height) and then becomes a wall of that level.
// time = O(m*n*log(m*n)), space = O(m*n)
public int trapRainWater(int[][] heightMap) {
    int m = heightMap.length, n = heightMap[0].length;
    if (m < 3 || n < 3) return 0;

    boolean[][] seen = new boolean[m][n];
    // min-heap of {height, row, col}
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
                pq.offer(new int[]{heightMap[i][j], i, j});
                seen[i][j] = true;
            }
        }
    }

    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int water = 0;

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int level = cur[0], r = cur[1], c = cur[2];

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n || seen[nr][nc]) continue;
            seen[nr][nc] = true;
            water += Math.max(0, level - heightMap[nr][nc]);          // trapped water
            pq.offer(new int[]{Math.max(level, heightMap[nr][nc]), nr, nc});
        }
    }
    return water;
}

# python
# LC 407 - Trapping Rain Water II
# IDEA: min-heap seeded with the border; pop the lowest wall, water on a lower neighbour
#       = level - height, and the neighbour joins the border at max(level, height)
# time = O(m*n*log(m*n)), space = O(m*n)
import heapq

def trapRainWater(heightMap):
    if not heightMap or len(heightMap) < 3 or len(heightMap[0]) < 3:
        return 0

    m, n = len(heightMap), len(heightMap[0])
    seen = [[False] * n for _ in range(m)]
    pq = []

    for i in range(m):
        for j in range(n):
            if i in (0, m - 1) or j in (0, n - 1):
                heapq.heappush(pq, (heightMap[i][j], i, j))
                seen[i][j] = True

    water = 0
    while pq:
        level, r, c = heapq.heappop(pq)
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc]:
                seen[nr][nc] = True
                water += max(0, level - heightMap[nr][nc])
                heapq.heappush(pq, (max(level, heightMap[nr][nc]), nr, nc))

    return water

# python
# LC 2617 - Minimum Number of Visited Cells in a Grid
# IDEA: row-major sweep; per-row and per-column min-heaps of (dist, index); pop entries whose
#       reach falls short of the current cell, the first one left gives dist + 1
# time = O(m*n*log(m+n)), space = O(m*n)
import heapq

def minimumVisitedCells(grid):
    m, n = len(grid), len(grid[0])
    dist = [[-1] * n for _ in range(m)]
    row_pqs = [[] for _ in range(m)]     # row_pqs[i]: (dist, col) of finalised cells in row i
    col_pqs = [[] for _ in range(n)]     # col_pqs[j]: (dist, row) of finalised cells in column j
    dist[0][0] = 1
    for i in range(m):
        for j in range(n):
            while row_pqs[i]:            # best cell to the left that still reaches column j
                d, prev_col = row_pqs[i][0]
                if prev_col + grid[i][prev_col] >= j:
                    if dist[i][j] == -1 or d + 1 < dist[i][j]:
                        dist[i][j] = d + 1
                    break
                heapq.heappop(row_pqs[i])        # cannot reach j, so no later column either
            while col_pqs[j]:            # best cell above that still reaches row i
                d, prev_row = col_pqs[j][0]
                if prev_row + grid[prev_row][j] >= i:
                    if dist[i][j] == -1 or d + 1 < dist[i][j]:
                        dist[i][j] = d + 1
                    break
                heapq.heappop(col_pqs[j])
            if dist[i][j] != -1 and grid[i][j] > 0:   # reachable and can jump: offer it forward
                heapq.heappush(row_pqs[i], (dist[i][j], j))
                heapq.heappush(col_pqs[j], (dist[i][j], i))
    return dist[m - 1][n - 1]

// java
// LC 2617 - Minimum Number of Visited Cells in a Grid
// IDEA: row-major sweep; per-row and per-column min-heaps of {dist, index}; poll entries that
//       can no longer reach the current cell, the first one left gives dist + 1
// time = O(m*n*log(m+n)), space = O(m*n)
public int minimumVisitedCells(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, -1);

    List<PriorityQueue<int[]>> rowPQs = new ArrayList<>();   // {dist, col} per row
    List<PriorityQueue<int[]>> colPQs = new ArrayList<>();   // {dist, row} per column
    for (int i = 0; i < m; i++) rowPQs.add(new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])));
    for (int j = 0; j < n; j++) colPQs.add(new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])));

    dist[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            PriorityQueue<int[]> rowPQ = rowPQs.get(i);
            while (!rowPQ.isEmpty()) {
                int[] top = rowPQ.peek();
                if (top[1] + grid[i][top[1]] >= j) {     // still reaches column j
                    if (dist[i][j] == -1 || top[0] + 1 < dist[i][j]) dist[i][j] = top[0] + 1;
                    break;
                }
                rowPQ.poll();                            // cannot reach j, nor any later column
            }
            PriorityQueue<int[]> colPQ = colPQs.get(j);
            while (!colPQ.isEmpty()) {
                int[] top = colPQ.peek();
                if (top[1] + grid[top[1]][j] >= i) {
                    if (dist[i][j] == -1 || top[0] + 1 < dist[i][j]) dist[i][j] = top[0] + 1;
                    break;
                }
                colPQ.poll();
            }
            if (dist[i][j] != -1 && grid[i][j] > 0) {
                rowPQ.offer(new int[]{dist[i][j], j});
                colPQ.offer(new int[]{dist[i][j], i});
            }
        }
    }
    return dist[m - 1][n - 1];
}

# python
# IDEA: a set guards the heap so each value is pushed once (LC 264 generates duplicates otherwise)
# time = O(n log n), space = O(n)
import heapq

def solve_with_unique_heap(nums):
    heap = []
    seen = set()
    for num in nums:
        if num not in seen:
            heapq.heappush(heap, num)
            seen.add(num)
    return heap

# python
# LC 632 - Smallest Range Covering Elements from K Lists
# IDEA: k-way merge frontier; window = [heap top, max of frontier]
# time = O(N log k), space = O(k)   N = total elements
import heapq

def smallestRange(nums):
    pq = [(row[0], i, 0) for i, row in enumerate(nums)]
    heapq.heapify(pq)
    cur_max = max(row[0] for row in nums)
    best = [pq[0][0], cur_max]

    while pq:
        val, i, j = heapq.heappop(pq)
        if cur_max - val < best[1] - best[0]:
            best = [val, cur_max]
        if j + 1 == len(nums[i]):
            break                      # a list is exhausted -> no more covering window
        nxt = nums[i][j + 1]
        cur_max = max(cur_max, nxt)
        heapq.heappush(pq, (nxt, i, j + 1))

    return best

# python
# IDEA: remove() only counts the value; pop() discards counted values when they reach the top
# time = O(log n) amortised per operation, space = O(n)
import heapq

class LazyHeap:
    def __init__(self):
        self.heap = []
        self.removed = {}   # val -> count of removed instances

    def push(self, val):
        heapq.heappush(self.heap, val)

    def remove(self, val):
        self.removed[val] = self.removed.get(val, 0) + 1

    def pop(self):
        while self.heap:
            val = self.heap[0]
            if self.removed.get(val, 0) > 0:
                heapq.heappop(self.heap)
                self.removed[val] -= 1
            else:
                return heapq.heappop(self.heap)
        return None

# Used in: LC 480 Sliding Window Median, LC 1825 Finding MK Average