题目描述
思路解析动画文字版
记住这条「各人推文按时间存·入堆·弹最新·补下一条」，下面每一步都在套它。
postTweet 给当前全局时间戳 +1 并把新推文插到该用户链头；follow 把对方加入关注集。t 越大表示越新。
getNewsFeed(小赵)：相关链有 4 条（自己 + 关注的 3 人）。堆容量 4，空位占位。先把每条链的链头(各自最新一条)入堆。
把 @小赵 的最新推文103(t9) 入堆： 先放到堆末尾(下标0)，再按「时间越新越靠堆顶」上浮。
把 @小钱 的最新推文203(t8) 入堆： 先放到堆末尾(下标1)，再按「时间越新越靠堆顶」上浮。
t8 不比父 t9 新，停止上浮，就位(标绿)。堆顶 t9 仍是当前最新。
把 @小孙 的最新推文303(t10) 入堆： 先放到堆末尾(下标2)，再按「时间越新越靠堆顶」上浮。
比较 t10 与父 t9：t10 更新(更晚)，上浮——和父交换。
交换完成，上浮到下标0。
把 @小李 的最新推文403(t11) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
比较 t11 与父 t8：t11 更新(更晚)，上浮——和父交换。
交换完成，上浮到下标1。
比较 t11 与父 t10：t11 更新(更晚)，上浮——和父交换。
交换完成，上浮到下标0。
堆顶 t11(@小李 推文403) 是当前所有链头里最新的，弹出接入新闻流。
推文403 接入新闻流(第1条)。把堆末元素 t8 暂放堆顶(标紫)，再下沉。
比较 t8 与更新的子节点 t10：子节点更新，下沉——交换。
交换完成，t8 沉到下标1。
t8 已不比子节点新，下沉结束(标绿)，堆顶 t10 又是当前最新。
@小李 刚被取走一条，补它链上下一条 推文402(t7) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
t7 不比父 t8 新，停止上浮，就位(标绿)。堆顶 t10 仍是当前最新。
堆顶 t10(@小孙 推文303) 是当前所有链头里最新的，弹出接入新闻流。
推文303 接入新闻流(第2条)。把堆末元素 t7 暂放堆顶(标紫)，再下沉。
比较 t7 与更新的子节点 t9：子节点更新，下沉——交换。
交换完成，t7 沉到下标2。
t7 已不比子节点新，下沉结束(标绿)，堆顶 t9 又是当前最新。
@小孙 刚被取走一条，补它链上下一条 推文302(t6) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
t6 不比父 t8 新，停止上浮，就位(标绿)。堆顶 t9 仍是当前最新。
堆顶 t9(@小赵 推文103) 是当前所有链头里最新的，弹出接入新闻流。
推文103 接入新闻流(第3条)。把堆末元素 t6 暂放堆顶(标紫)，再下沉。
比较 t6 与更新的子节点 t8：子节点更新，下沉——交换。
交换完成，t6 沉到下标1。
t6 已不比子节点新，下沉结束(标绿)，堆顶 t8 又是当前最新。
@小赵 刚被取走一条，补它链上下一条 推文102(t5) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
t5 不比父 t6 新，停止上浮，就位(标绿)。堆顶 t8 仍是当前最新。
堆顶 t8(@小钱 推文203) 是当前所有链头里最新的，弹出接入新闻流。
推文203 接入新闻流(第4条)。把堆末元素 t5 暂放堆顶(标紫)，再下沉。
比较 t5 与更新的子节点 t7：子节点更新，下沉——交换。
交换完成，t5 沉到下标2。
t5 已不比子节点新，下沉结束(标绿)，堆顶 t7 又是当前最新。
@小钱 刚被取走一条，补它链上下一条 推文202(t3) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
t3 不比父 t6 新，停止上浮，就位(标绿)。堆顶 t7 仍是当前最新。
堆顶 t7(@小李 推文402) 是当前所有链头里最新的，弹出接入新闻流。
推文402 接入新闻流(第5条)。把堆末元素 t3 暂放堆顶(标紫)，再下沉。
比较 t3 与更新的子节点 t6：子节点更新，下沉——交换。
交换完成，t3 沉到下标1。
t3 已不比子节点新，下沉结束(标绿)，堆顶 t6 又是当前最新。
@小李 刚被取走一条，补它链上下一条 推文401(t4) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
比较 t4 与父 t3：t4 更新(更晚)，上浮——和父交换。
交换完成，上浮到下标1。
t4 不比父 t6 新，停止上浮，就位(标绿)。堆顶 t6 仍是当前最新。
堆顶 t6(@小孙 推文302) 是当前所有链头里最新的，弹出接入新闻流。
推文302 接入新闻流(第6条)。把堆末元素 t3 暂放堆顶(标紫)，再下沉。
比较 t3 与更新的子节点 t5：子节点更新，下沉——交换。
交换完成，t3 沉到下标2。
t3 已不比子节点新，下沉结束(标绿)，堆顶 t5 又是当前最新。
@小孙 刚被取走一条，补它链上下一条 推文301(t2) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
t2 不比父 t4 新，停止上浮，就位(标绿)。堆顶 t5 仍是当前最新。
堆顶 t5(@小赵 推文102) 是当前所有链头里最新的，弹出接入新闻流。
推文102 接入新闻流(第7条)。把堆末元素 t2 暂放堆顶(标紫)，再下沉。
比较 t2 与更新的子节点 t4：子节点更新，下沉——交换。
交换完成，t2 沉到下标1。
t2 已不比子节点新，下沉结束(标绿)，堆顶 t4 又是当前最新。
@小赵 刚被取走一条，补它链上下一条 推文101(t1) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
t1 不比父 t2 新，停止上浮，就位(标绿)。堆顶 t4 仍是当前最新。
堆顶 t4(@小李 推文401) 是当前所有链头里最新的，弹出接入新闻流。
推文401 接入新闻流(第8条)。把堆末元素 t1 暂放堆顶(标紫)，再下沉。
比较 t1 与更新的子节点 t3：子节点更新，下沉——交换。
交换完成，t1 沉到下标2。
t1 已不比子节点新，下沉结束(标绿)，堆顶 t3 又是当前最新。
@小李 的推文链走空，无可补；堆里还剩 3 个链头(堆顶 t3，标蓝)继续。
堆顶 t3(@小钱 推文202) 是当前所有链头里最新的，弹出接入新闻流。
推文202 接入新闻流(第9条)。把堆末元素 t1 暂放堆顶(标紫)，再下沉。
比较 t1 与更新的子节点 t2：子节点更新，下沉——交换。
交换完成，t1 沉到下标1。
t1 已不比子节点新，下沉结束(标绿)，堆顶 t2 又是当前最新。
@小钱 刚被取走一条，补它链上下一条 推文201(t0) 入堆： 先放到堆末尾(下标2)，再按「时间越新越靠堆顶」上浮。
t0 不比父 t2 新，停止上浮，就位(标绿)。堆顶 t2 仍是当前最新。
堆顶 t2(@小孙 推文301) 是当前所有链头里最新的，弹出接入新闻流。
推文301 接入新闻流(第10条)。把堆末元素 t0 暂放堆顶(标紫)，再下沉。
比较 t0 与更新的子节点 t1：子节点更新，下沉——交换。
交换完成，t0 沉到下标1。
t0 已不比子节点新，下沉结束(标绿)，堆顶 t1 又是当前最新。
已取满 10 条（或堆空）。新闻流按时间从新到旧：推文403 → 推文303 → 推文103 → 推文203 → 推文402 → 推文302 → 推文102 → 推文401 → 推文202 → 推文301。getNewsFeed 完成。
没关注任何人、关注的人没发推、总数不足 10 三个边界先想清。
两个高频追问：为何用链表存推文、关注者极多时如何优化。
参考代码
class Twitter { private int time = 0; // 全局时间戳 static class Tweet { int id, t; Tweet next; // 推文链节点 Tweet(int id, int t){ this.id=id; this.t=t; } } private Map<Integer,Tweet> tweets = new HashMap<>(); // 用户→推文链头(最新) private Map<Integer,Set<Integer>> follows = new HashMap<>(); // 用户→关注集 public void postTweet(int u, int id){ Tweet h = new Tweet(id, time++); h.next = tweets.get(u); tweets.put(u, h); // 插到链头 } public void follow(int u, int v){ follows.computeIfAbsent(u, k->new HashSet<>()).add(v); } public void unfollow(int u, int v){ if(u!=v && follows.containsKey(u)) follows.get(u).remove(v); } public List<Integer> getNewsFeed(int u){ // 最大堆：时间越新越靠堆顶 PriorityQueue<Tweet> pq = new PriorityQueue<>((a,b) -> b.t - a.t); Set<Integer> src = new HashSet<>(follows.getOrDefault(u, new HashSet<>())); src.add(u); // 包含自己 for(int id : src) if(tweets.get(id)!=null) pq.offer(tweets.get(id)); // 各链头入堆 List<Integer> res = new ArrayList<>(); while(!pq.isEmpty() && res.size() < 10){ Tweet t = pq.poll(); // 弹最新 res.add(t.id); if(t.next != null) pq.offer(t.next); // 补该链下一条 } return res; }}复杂度
- postTweet：O(1)，新推文插到该用户链头，常数时间
- follow/unfollow：O(1)，关注集（哈希集合）增删一项
- getNewsFeed：O(K + L·logK)，K=相关用户数，L=10(取的条数)；各链头入堆 + 弹补各 O(logK)
易错点
面试追问把动画讲成自己的话
追问为什么用链表存推文而不是普通数组？
追问关注者很多、每人推文很多时会慢吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数据流的中位数
LeetCode 295 · 困难 · 沿着 堆 / 优先队列 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题