§1

题目描述

设计发推、关注、取消关注、获取最近 10 条动态。

示例 = postTweet(1,5), getNewsFeed(1) → [5]

§2

思路解析动画文字版

每次把所有推文全局排序会很慢。

每个用户保留自己的推文链，拉取 feed 时只把自己和关注者的最新推文放进最大堆。

① feed ＝自己 + 关注者，按时间取最近 10 条：user1 关注 user2。要「自己 + 关注的人」所有推文里最近 10 条。每人时间线已有序 → 用大顶堆做 k 路归并(k=关注数+1)。

② 各被关注者(含自己)的最新一条入堆：把 u1 的最新(推文3,t=2)和 u2 的最新(推文6,t=3)放进堆，堆顶＝时间最新。💡实现技巧：代码里把时间戳「取负」、用最小堆，弹出最小(负得最多)正好是时间最新的，效果等同大顶堆。

③ 弹出堆顶推文6(t=3) 进 feed，补 u2 的上一条推文5(t=1)：弹出最新的推文6 加入 feed；再把它作者 u2 的「上一条」推文5(t=1) 补进堆，保证不漏 u2 的历史。

④ 弹出推文3(t=2) 进 feed，u1 没有更早的：堆顶现在是推文3(t=2) → 弹出加入 feed。u1 没有更早的推文，不补充。

⑤ 弹出推文5(t=1) → feed ＝ [6, 3, 5]：最后弹出推文5(t=1)。feed 从新到旧＝ [6,3,5]。实际只取前 10 条就停止。

一句话记住：每个用户保留自己的推文链，拉取 feed 时只把自己和关注者的最新推文放进最大堆。

边界三连：本题真边界：零关注、空时间线、超 10 条。

⑥ 雷区：为什么用堆而不是把所有推文排序？：把所有人所有推文全收集再排序是 O(N log N)。利用「每人时间线已有序」做 k 路归并：堆里只放 k 个候选(每人当前最新)，取 10 条只需约 10·log k 次堆操作，远小于全排序。

面试追问 · 核心思路：思路：每用户存推文列表+关注集合；feed 用堆 k 路归并取前 10。

面试追问 · follow/unfollow 为何 O(1)：关注关系用 set 存，增删查都是 O(1)。

面试追问 · 复杂度：复杂度：post/follow O(1)，getNewsFeed O(10·log k)。

这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=heap 连刷同类题；卡住时用 AI 答疑问“feed 为什么用堆归并”。

§3

参考代码

class Twitter:    def __init__(self):        self.time = 0        self.tweets = {}        self.following = {}    def postTweet(self, userId, tweetId):        self.time -= 1        self.tweets.setdefault(userId, []).append((self.time, tweetId))    def getNewsFeed(self, userId):        import heapq        self.following.setdefault(userId, set()).add(userId)        heap = []        for uid in self.following[userId]:            arr = self.tweets.get(uid, [])            if arr:                i = len(arr) - 1                t, tid = arr[i]                heapq.heappush(heap, (t, tid, uid, i - 1))        ans = []        while heap and len(ans) < 10:            t, tid, uid, i = heapq.heappop(heap)            ans.append(tid)            if i >= 0:                nt, ntid = self.tweets[uid][i]                heapq.heappush(heap, (nt, ntid, uid, i - 1))        return ans    def follow(self, followerId, followeeId):        self.following.setdefault(followerId, set()).add(followeeId)    def unfollow(self, followerId, followeeId):        if followerId != followeeId:            self.following.setdefault(followerId, set()).discard(followeeId)

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间复杂度：getNewsFeed O(10·log k)，post/follow/unfollow 均 O(1)；feed 堆归并取 10 条
空间复杂度：O(N + U)，N 条推文 + 关注关系；堆只占 O(k)

§5

可套用的代码模板

记牢：每人时间线有序 → 堆放各人最新 → 弹最新进 feed、补该人上一条 → 取满 10 条。

Python

# 设计推特（堆 k 路归并）骨架postTweet: self.time -= 1; tweets[user].append((self.time, tid))   # 自减戳(取负)follow/unfollow: following[user].add/discard(other)def getNewsFeed(user):    following[user].add(user)            # 把自己也算上    heap = [每个被关注者最新一条 (t, tid, uid, idx)]    feed = []    while heap and len(feed) < 10:        t, tid, uid, i = heappop(heap)   # 弹出全局最新        feed.append(tid)        if i >= 0: heappush(heap, 该用户上一条)   # 补历史    return feed

§6

易错点

✗ 错误写法：getNewsFeed 收集所有推文再排序

✓ 正确写法：大顶堆 k 路归并，只取前 10

每人时间线已有序，堆合并取前 10 是 O(10 log k)，全排序是 O(N log N)。

✗ 错误写法：忘了 feed 要包含自己的推文

✓ 正确写法：把自己也并入关注集合一起合并

用户自己发的推文也要出现在自己的 feed 里。

✗ 错误写法：用真实时间、可能重复

✓ 正确写法：用全局自增计数当时间戳

自增戳保证严格有序，堆能准确比较先后。

面试追问把动画讲成自己的话

追问整体怎么设计？

每个用户：一条 (时间戳, tweetId) 列表(按发推顺序)+一个关注 set。postTweet 用全局自增戳 append，O(1)。follow/unfollow 改 set，O(1)。getNewsFeed：把「自己+关注者」每人的最新推文放进大顶堆，弹出最新加入 feed、补该用户上一条，弹满 10 条或堆空为止。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 堆 / 优先队列 7/7

数据流的中位数

LeetCode 295 · 困难 · 沿着堆 / 优先队列继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

299道动画图解

37节语音讲解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

class Twitter: def __init__(self): self.time = 0 self.tweets = {} self.following = {} def postTweet(self, userId, tweetId): self.time -= 1 self.tweets.setdefault(userId, []).append((self.time, tweetId)) def getNewsFeed(self, userId): import heapq self.following.setdefault(userId, set()).add(userId) heap = [] for uid in self.following[userId]: arr = self.tweets.get(uid, []) if arr: i = len(arr) - 1 t, tid = arr[i] heapq.heappush(heap, (t, tid, uid, i - 1)) ans = [] while heap and len(ans) < 10: t, tid, uid, i = heapq.heappop(heap) ans.append(tid) if i >= 0: nt, ntid = self.tweets[uid][i] heapq.heappush(heap, (nt, ntid, uid, i - 1)) return ans def follow(self, followerId, followeeId): self.following.setdefault(followerId, set()).add(followeeId) def unfollow(self, followerId, followeeId): if followerId != followeeId: self.following.setdefault(followerId, set()).discard(followeeId)

# 设计推特（堆 k 路归并）骨架postTweet: self.time -= 1; tweets[user].append((self.time, tid)) # 自减戳(取负)follow/unfollow: following[user].add/discard(other)def getNewsFeed(user): following[user].add(user) # 把自己也算上 heap = [每个被关注者最新一条 (t, tid, uid, idx)] feed = [] while heap and len(feed) < 10: t, tid, uid, i = heappop(heap) # 弹出全局最新 feed.append(tid) if i >= 0: heappush(heap, 该用户上一条) # 补历史 return feed