heap 可以用来干什么？

[azl397985856]

1. 求 k

[692] 前K个高频单词

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        counter = collections.Counter(words)
        h = [(-v, k) for k, v in counter.items()]
        return list(map(lambda a: a[1], heapq.nsmallest(k, h)))

2. 从 k 个列表中各取一个数，使得这 k 个数中的最大值与最小值的差最小。

[632] 最小区间

class Solution:
    def smallestRange(self, martrix: List[List[int]]) -> List[int]:
        l, r = -10**9, 10**9
        # 每一个行放一个数字进堆，并维持堆的大小不变。堆在整个过程都是每个行有且仅有一个
        pq = [(row[0], i, 0) for i, row in enumerate(martrix)]
        heapq.heapify(pq)
        # 维持当前堆中的最大值
        max_v = max(row[0] for row in martrix)

        while True:
            min_v, row, col = heapq.heappop(pq)
            if max_v - min_v < r - l:
                l, r = min_v, max_v
            if col == len(martrix[row]) - 1: return [l, r]
            heapq.heappush(pq, (martrix[row][col + 1], row, col + 1))
            max_v = max(max_v, martrix[row][col + 1])

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.