设计推特 图解题解

这道题到底在问什么

输入

小赵关注小钱/小孙/小李；四人交错发推；getNewsFeed(小赵)

输出

按发推时间从新到旧取最近10条

最优解：一步一步想明白

1. 3记住这条「各人推文按时间存·入堆·弹最新·补下一条」，下面每一步都在套它。
2. 4postTweet 给当前全局时间戳 +1 并把新推文插到该用户链头；follow 把对方加入关注集。t 越大表示越新。
3. 5getNewsFeed(小赵)：相关链有 4 条（自己 + 关注的 3 人）。堆容量 4，空位占位。先把每条链的链头(各自最新一条)入堆。
4. 6把 @小赵 的最新推文103(t9) 入堆： 先放到堆末尾(下标0)，再按「时间越新越靠堆顶」上浮。
5. 7把 @小钱 的最新推文203(t8) 入堆： 先放到堆末尾(下标1)，再按「时间越新越靠堆顶」上浮。
6. 8t8 不比父 t9 新，停止上浮，就位(标绿)。堆顶 t9 仍是当前最新。
7. 9把 @小孙 的最新推文303(t10) 入堆： 先放到堆末尾(下标2)，再按「时间越新越靠堆顶」上浮。
8. 10比较 t10 与父 t9：t10 更新(更晚)，上浮——和父交换。
9. 11交换完成，上浮到下标0。
10. 12把 @小李 的最新推文403(t11) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
11. 13比较 t11 与父 t8：t11 更新(更晚)，上浮——和父交换。
12. 14交换完成，上浮到下标1。
13. 15比较 t11 与父 t10：t11 更新(更晚)，上浮——和父交换。
14. 16交换完成，上浮到下标0。
15. 17堆顶 t11(@小李 推文403) 是当前所有链头里最新的，弹出接入新闻流。
16. 18推文403 接入新闻流(第1条)。把堆末元素 t8 暂放堆顶(标紫)，再下沉。
17. 19比较 t8 与更新的子节点 t10：子节点更新，下沉——交换。
18. 20交换完成，t8 沉到下标1。
19. 21t8 已不比子节点新，下沉结束(标绿)，堆顶 t10 又是当前最新。
20. 22@小李 刚被取走一条，补它链上下一条 推文402(t7) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
21. 23t7 不比父 t8 新，停止上浮，就位(标绿)。堆顶 t10 仍是当前最新。
22. 24堆顶 t10(@小孙 推文303) 是当前所有链头里最新的，弹出接入新闻流。
23. 25推文303 接入新闻流(第2条)。把堆末元素 t7 暂放堆顶(标紫)，再下沉。
24. 26比较 t7 与更新的子节点 t9：子节点更新，下沉——交换。
25. 27交换完成，t7 沉到下标2。
26. 28t7 已不比子节点新，下沉结束(标绿)，堆顶 t9 又是当前最新。
27. 29@小孙 刚被取走一条，补它链上下一条 推文302(t6) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
28. 30t6 不比父 t8 新，停止上浮，就位(标绿)。堆顶 t9 仍是当前最新。
29. 31堆顶 t9(@小赵 推文103) 是当前所有链头里最新的，弹出接入新闻流。
30. 32推文103 接入新闻流(第3条)。把堆末元素 t6 暂放堆顶(标紫)，再下沉。
31. 33比较 t6 与更新的子节点 t8：子节点更新，下沉——交换。
32. 34交换完成，t6 沉到下标1。
33. 35t6 已不比子节点新，下沉结束(标绿)，堆顶 t8 又是当前最新。
34. 36@小赵 刚被取走一条，补它链上下一条 推文102(t5) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
35. 37t5 不比父 t6 新，停止上浮，就位(标绿)。堆顶 t8 仍是当前最新。
36. 38堆顶 t8(@小钱 推文203) 是当前所有链头里最新的，弹出接入新闻流。
37. 39推文203 接入新闻流(第4条)。把堆末元素 t5 暂放堆顶(标紫)，再下沉。
38. 40比较 t5 与更新的子节点 t7：子节点更新，下沉——交换。
39. 41交换完成，t5 沉到下标2。
40. 42t5 已不比子节点新，下沉结束(标绿)，堆顶 t7 又是当前最新。
41. 43@小钱 刚被取走一条，补它链上下一条 推文202(t3) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
42. 44t3 不比父 t6 新，停止上浮，就位(标绿)。堆顶 t7 仍是当前最新。
43. 45堆顶 t7(@小李 推文402) 是当前所有链头里最新的，弹出接入新闻流。
44. 46推文402 接入新闻流(第5条)。把堆末元素 t3 暂放堆顶(标紫)，再下沉。
45. 47比较 t3 与更新的子节点 t6：子节点更新，下沉——交换。
46. 48交换完成，t3 沉到下标1。
47. 49t3 已不比子节点新，下沉结束(标绿)，堆顶 t6 又是当前最新。
48. 50@小李 刚被取走一条，补它链上下一条 推文401(t4) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
49. 51比较 t4 与父 t3：t4 更新(更晚)，上浮——和父交换。
50. 52交换完成，上浮到下标1。
51. 53t4 不比父 t6 新，停止上浮，就位(标绿)。堆顶 t6 仍是当前最新。
52. 54堆顶 t6(@小孙 推文302) 是当前所有链头里最新的，弹出接入新闻流。
53. 55推文302 接入新闻流(第6条)。把堆末元素 t3 暂放堆顶(标紫)，再下沉。
54. 56比较 t3 与更新的子节点 t5：子节点更新，下沉——交换。
55. 57交换完成，t3 沉到下标2。
56. 58t3 已不比子节点新，下沉结束(标绿)，堆顶 t5 又是当前最新。
57. 59@小孙 刚被取走一条，补它链上下一条 推文301(t2) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
58. 60t2 不比父 t4 新，停止上浮，就位(标绿)。堆顶 t5 仍是当前最新。
59. 61堆顶 t5(@小赵 推文102) 是当前所有链头里最新的，弹出接入新闻流。
60. 62推文102 接入新闻流(第7条)。把堆末元素 t2 暂放堆顶(标紫)，再下沉。
61. 63比较 t2 与更新的子节点 t4：子节点更新，下沉——交换。
62. 64交换完成，t2 沉到下标1。
63. 65t2 已不比子节点新，下沉结束(标绿)，堆顶 t4 又是当前最新。
64. 66@小赵 刚被取走一条，补它链上下一条 推文101(t1) 入堆： 先放到堆末尾(下标3)，再按「时间越新越靠堆顶」上浮。
65. 67t1 不比父 t2 新，停止上浮，就位(标绿)。堆顶 t4 仍是当前最新。
66. 68堆顶 t4(@小李 推文401) 是当前所有链头里最新的，弹出接入新闻流。
67. 69推文401 接入新闻流(第8条)。把堆末元素 t1 暂放堆顶(标紫)，再下沉。
68. 70比较 t1 与更新的子节点 t3：子节点更新，下沉——交换。
69. 71交换完成，t1 沉到下标2。
70. 72t1 已不比子节点新，下沉结束(标绿)，堆顶 t3 又是当前最新。
71. 73@小李 的推文链走空，无可补；堆里还剩 3 个链头(堆顶 t3，标蓝)继续。
72. 74堆顶 t3(@小钱 推文202) 是当前所有链头里最新的，弹出接入新闻流。
73. 75推文202 接入新闻流(第9条)。把堆末元素 t1 暂放堆顶(标紫)，再下沉。
74. 76比较 t1 与更新的子节点 t2：子节点更新，下沉——交换。
75. 77交换完成，t1 沉到下标1。
76. 78t1 已不比子节点新，下沉结束(标绿)，堆顶 t2 又是当前最新。
77. 79@小钱 刚被取走一条，补它链上下一条 推文201(t0) 入堆： 先放到堆末尾(下标2)，再按「时间越新越靠堆顶」上浮。
78. 80t0 不比父 t2 新，停止上浮，就位(标绿)。堆顶 t2 仍是当前最新。
79. 81堆顶 t2(@小孙 推文301) 是当前所有链头里最新的，弹出接入新闻流。
80. 82推文301 接入新闻流(第10条)。把堆末元素 t0 暂放堆顶(标紫)，再下沉。
81. 83比较 t0 与更新的子节点 t1：子节点更新，下沉——交换。
82. 84交换完成，t0 沉到下标1。
83. 85t0 已不比子节点新，下沉结束(标绿)，堆顶 t1 又是当前最新。
84. 86已取满 10 条（或堆空）。新闻流按时间从新到旧：推文403 → 推文303 → 推文103 → 推文203 → 推文402 → 推文302 → 推文102 → 推文401 → 推文202 → 推文301。getNewsFeed 完成。

⚠️ 容易写错的地方

完整代码（Java / Python / C++）

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;
    }
}

import heapq
class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = {}                      # uid -> [(-t, id), ...] 头部最新
        self.follows = {}                     # uid -> set
    def postTweet(self, u, tid):
        self.tweets.setdefault(u, []).append((self.time, tid)); self.time += 1
    def follow(self, u, v):
        self.follows.setdefault(u, set()).add(v)
    def unfollow(self, u, v):
        if u != v: self.follows.setdefault(u, set()).discard(v)
    def getNewsFeed(self, u):
        src = set(self.follows.get(u, set())) | {u}
        h = []                                # 最大堆(用负时间戳)
        for uid in src:
            lst = self.tweets.get(uid)
            if lst:
                i = len(lst) - 1                  # 该用户最新一条的下标
                t, tid = lst[i]
                heapq.heappush(h, (-t, tid, uid, i))
        res = []
        while h and len(res) < 10:
            nt, tid, uid, i = heapq.heappop(h)    # 弹最新
            res.append(tid)
            if i > 0:                             # 补该链下一条(更旧)
                pt, ptid = self.tweets[uid][i-1]
                heapq.heappush(h, (-pt, ptid, uid, i-1))
        return res

class Twitter {
    int time = 0;
    struct Tweet { int id, t; Tweet* next; };
    unordered_map<int, Tweet*> tweets;          // uid -> 链头(最新)
    unordered_map<int, unordered_set<int>> follows;
public:
    void postTweet(int u, int id){
        tweets[u] = new Tweet{id, time++, tweets.count(u)?tweets[u]:nullptr}; }
    void follow(int u, int v){ follows[u].insert(v); }
    void unfollow(int u, int v){ if(u!=v) follows[u].erase(v); }
    vector<int> getNewsFeed(int u){
        auto cmp = [](Tweet* a, Tweet* b){ return a->t < b->t; }; // 最大堆
        priority_queue<Tweet*, vector<Tweet*>, decltype(cmp)> pq(cmp);
        auto src = follows[u]; src.insert(u);
        for(int id : src) if(tweets.count(id)) pq.push(tweets[id]);
        vector<int> res;
        while(!pq.empty() && res.size() < 10){
            Tweet* t = pq.top(); pq.pop();          // 弹最新
            res.push_back(t->id);
            if(t->next) pq.push(t->next);           // 补下一条
        }
        return res;
    }
};

复杂度

面试官可能追问