设计推特 图解题解

这道题到底在问什么

示例

postTweet(1,5), getNewsFeed(1) → [5]

最优解：一步一步想明白

1. 3每次把所有推文全局排序会很慢。
2. 4每个用户保留自己的推文链，拉取 feed 时只把自己和关注者的最新推文放进最大堆。
3. 5user1 关注 user2。要「自己 + 关注的人」所有推文里最近 10 条。每人时间线已有序 → 用大顶堆做 k 路归并(k=关注数+1)。
4. 6把 u1 的最新(推文3,t=2)和 u2 的最新(推文6,t=3)放进堆，堆顶 ＝ 时间最新。💡实现技巧：代码里把时间戳「取负」、用最小堆，弹出最小(负得最多)正好是时间最新的，效果等同大顶堆。
5. 7弹出最新的 推文6 加入 feed；再把它作者 u2 的「上一条」推文5(t=1) 补进堆，保证不漏 u2 的历史。
6. 8堆顶现在是 推文3(t=2) → 弹出加入 feed。u1 没有更早的推文，不补充。
7. 9最后弹出 推文5(t=1)。feed 从新到旧 ＝ [6,3,5]。实际只取前 10 条就停止。
8. 12一句话记住：每个用户保留自己的推文链，拉取 feed 时只把自己和关注者的最新推文放进最大堆。
9. 15把所有人所有推文全收集再排序是 O(N log N)。利用「每人时间线已有序」做 k 路归并：堆里只放 k 个候选(每人当前最新)，取 10 条只需约 10·log k 次堆操作，远小于全排序。
10. 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=heap 连刷同类题；卡住时用 AI 答疑问“feed 为什么用堆归并”。

⚠️ 容易写错的地方

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

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)

class Twitter {
    int timer = 0;
    unordered_map<int, vector<pair<int,int>>> tweets;
    unordered_map<int, unordered_set<int>> followees;
public:
    void postTweet(int userId, int tweetId) {
        tweets[userId].push_back({--timer, tweetId});
    }
    vector<int> getNewsFeed(int userId) {
        followees[userId].insert(userId);
        using T = tuple<int,int,int,int>;
        priority_queue<T, vector<T>, greater<T>> pq;
        for (int uid : followees[userId]) {
            auto& v = tweets[uid];
            if (!v.empty()) {
                int i = v.size() - 1;
                pq.push({v[i].first, v[i].second, uid, i - 1});
            }
        }
        vector<int> ans;
        while (!pq.empty() && ans.size() < 10) {
            auto [t, tid, uid, i] = pq.top(); pq.pop();
            ans.push_back(tid);
            if (i >= 0) pq.push({tweets[uid][i].first, tweets[uid][i].second, uid, i - 1});
        }
        return ans;
    }
    void follow(int followerId, int followeeId) { followees[followerId].insert(followeeId); }
    void unfollow(int followerId, int followeeId) { if (followerId != followeeId) followees[followerId].erase(followeeId); }
};

class Twitter {
    int time = 0;
    Map<Integer, List<int[]>> tweets = new HashMap<>();
    Map<Integer, Set<Integer>> follow = new HashMap<>();
    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{--time, tweetId});
    }
    public List<Integer> getNewsFeed(int userId) {
        follow.computeIfAbsent(userId, k -> new HashSet<>()).add(userId);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] - b[0]);
        for (int uid : follow.get(userId)) {
            List<int[]> arr = tweets.getOrDefault(uid, new ArrayList<>());
            if (!arr.isEmpty()) {
                int i = arr.size() - 1;
                pq.offer(new int[]{arr.get(i)[0], arr.get(i)[1], uid, i - 1});
            }
        }
        List<Integer> ans = new ArrayList<>();
        while (!pq.isEmpty() && ans.size() < 10) {
            int[] cur = pq.poll();
            ans.add(cur[1]);
            if (cur[3] >= 0) {
                int[] next = tweets.get(cur[2]).get(cur[3]);
                pq.offer(new int[]{next[0], next[1], cur[2], cur[3] - 1});
            }
        }
        return ans;
    }
    public void follow(int followerId, int followeeId) { follow.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId); }
    public void unfollow(int followerId, int followeeId) { if (followerId != followeeId) follow.computeIfAbsent(followerId, k -> new HashSet<>()).remove(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

复杂度

面试官可能追问