Medium

题目描述

你需要设计一个竞价系统，能够实时管理多个用户的竞价。

每个竞价都关联着一个 userId、一个 itemId 和一个 bidAmount。

实现 AuctionSystem 类：

  • AuctionSystem()：初始化 AuctionSystem 对象。
  • void addBid(int userId, int itemId, int bidAmount)：为 itemId 添加一个由 userId 出价 bidAmount 的新竞价。如果同一个 userId 已经对 itemId 有竞价，则用新的 bidAmount 替换它。
  • void updateBid(int userId, int itemId, int newAmount)：将 userId 对 itemId 的现有竞价更新为 newAmount。保证该竞价存在。
  • void removeBid(int userId, int itemId)：移除 userId 对 itemId 的竞价。保证该竞价存在。
  • int getHighestBidder(int itemId)：返回 itemId 的最高出价者的 userId。如果多个用户有相同的最高出价，返回 userId 最大的用户。如果该物品没有竞价，返回 -1。

示例 1：

输入：
["AuctionSystem", "addBid", "addBid", "getHighestBidder", "updateBid", "getHighestBidder", "removeBid", "getHighestBidder", "getHighestBidder"]
[[], [1, 7, 5], [2, 7, 6], [7], [1, 7, 8], [7], [2, 7], [7], [3]]

输出：
[null, null, null, 2, null, 1, null, 1, -1]

约束：

  • 1 <= userId, itemId <= 5 * 10^4
  • 1 <= bidAmount, newAmount <= 10^9
  • 最多调用 addBid、updateBid、removeBid 和 getHighestBidder 总共 5 * 10^4 次
  • 输入保证对于 updateBid 和 removeBid，给定 userId 对给定 itemId 的竞价是有效的

解题思路

这道题需要设计一个高效的竞价系统。核心在于快速找到每个物品的最高出价者。

核心思路：

  1. 数据结构选择：使用哈希表 itemToBids 将每个 itemId 映射到该物品的所有竞价信息。每个物品的竞价用有序集合维护，按 (bidAmount, userId) 排序。

  2. 排序规则：为了快速获取最高出价者，我们按出价金额升序排列，相同金额时按用户ID升序排列。这样最高出价者就在集合的末尾。

  3. 操作实现：

    • addBid：先删除用户的旧竞价（如果存在），再插入新竞价
    • updateBid：等价于先删除再添加
    • removeBid：直接从有序集合中删除对应竞价
    • getHighestBidder：返回有序集合末尾元素的用户ID

  4. 快速查找：使用额外的哈希表 userItemToBid 记录每个用户对每个物品的当前出价，便于快速定位和删除。

时间复杂度：所有操作都是 O(log n)，其中 n 是该物品的竞价数量。空间复杂度为 O(总竞价数)。

代码实现

class AuctionSystem {
private:
    map<int, set<pair<int, int>>> itemToBids;
    map<pair<int, int>, int> userItemToBid;
    
public:
    AuctionSystem() {
        
    }
    
    void addBid(int userId, int itemId, int bidAmount) {
        removeBidIfExists(userId, itemId);
        itemToBids[itemId].insert({bidAmount, userId});
        userItemToBid[{userId, itemId}] = bidAmount;
    }
    
    void updateBid(int userId, int itemId, int newAmount) {
        addBid(userId, itemId, newAmount);
    }
    
    void removeBid(int userId, int itemId) {
        removeBidIfExists(userId, itemId);
    }
    
    int getHighestBidder(int itemId) {
        if (itemToBids[itemId].empty()) {
            return -1;
        }
        return itemToBids[itemId].rbegin()->second;
    }
    
private:
    void removeBidIfExists(int userId, int itemId) {
        auto key = make_pair(userId, itemId);
        if (userItemToBid.find(key) != userItemToBid.end()) {
            int oldAmount = userItemToBid[key];
            itemToBids[itemId].erase({oldAmount, userId});
            userItemToBid.erase(key);
        }
    }
};

from sortedcontainers import SortedList

class AuctionSystem:

    def __init__(self):
        self.item_to_bids = {}
        self.user_item_to_bid = {}

    def addBid(self, userId: int, itemId: int, bidAmount: int) -> None:
        self._remove_bid_if_exists(userId, itemId)
        
        if itemId not in self.item_to_bids:
            self.item_to_bids[itemId] = SortedList()
        
        self.item_to_bids[itemId].add((bidAmount, userId))
        self.user_item_to_bid[(userId, itemId)] = bidAmount

    def updateBid(self, userId: int, itemId: int, newAmount: int) -> None:
        self.addBid(userId, itemId, newAmount)

    def removeBid(self, userId: int, itemId: int) -> None:
        self._remove_bid_if_exists(userId, itemId)

    def getHighestBidder(self, itemId: int) -> int:
        if itemId not in self.item_to_bids or not self.item_to_bids[itemId]:
            return -1
        return self.item_to_bids[itemId][-1][1]
    
    def _remove_bid_if_exists(self, userId: int, itemId: int) -> None:
        key = (userId, itemId)
        if key in self.user_item_to_bid:
            old_amount = self.user_item_to_bid[key]
            self.item_to_bids[itemId].remove((old_amount, userId))
            del self.user_item_to_bid[key]

public class AuctionSystem {
    private Dictionary<int, SortedSet<(int bidAmount, int userId)>> itemToBids;
    private Dictionary<(int userId, int itemId), int> userItemToBid;

    public AuctionSystem() {
        itemToBids = new Dictionary<int, SortedSet<(int, int)>>();
        userItemToBid = new Dictionary<(int, int), int>();
    }
    
    public void AddBid(int userId, int itemId, int bidAmount) {
        RemoveBidIfExists(userId, itemId);
        
        if (!itemToBids.ContainsKey(itemId)) {
            itemToBids[itemId] = new SortedSet<(int, int)>();
        }
        
        itemToBids[itemId].Add((bidAmount, userId));
        userItemToBid[(userId, itemId)] = bidAmount;
    }
    
    public void UpdateBid(int userId, int itemId, int newAmount) {
        AddBid(userId, itemId, newAmount);
    }
    
    public void RemoveBid(int userId, int itemId) {
        RemoveBidIfExists(userId, itemId);
    }
    
    public int GetHighestBidder(int itemId) {
        if (!itemToBids.ContainsKey(itemId) || itemToBids[itemId].Count == 0) {
            return -1;
        }
        return itemToBids[itemId].Max.userId;
    }
    
    private void RemoveBidIfExists(int userId, int itemId) {
        var key = (userId, itemId);
        if (userItemToBid.ContainsKey(key)) {
            int oldAmount = userItemToBid[key];
            itemToBids[itemId].Remove((oldAmount, userId));
            userItemToBid.Remove(key);
        }
    }
}

var AuctionSystem = function() {
    this.itemToBids = new Map();
    this.userItemToBid = new Map();
};

AuctionSystem.prototype.addBid = function(userId, itemId, bidAmount) {
    this.removeBidIfExists(userId, itemId);
    
    if (!this.itemToBids.has(itemId)) {
        this.itemToBids.set(itemId, []);
    }
    
    const bids = this.itemToBids.get(itemId);
    bids.push([bidAmount, userId]);
    bids.sort((a, b) => a[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
addBidO(log n)O(1)
updateBidO(log n)O(1)
removeBidO(log n)O(1)
getHighestBidderO(1)O(1)
总体空间-O(总竞价数)

其中 n 是单个物品的竞价数量。使用有序集合保证了高效的插入、删除和查找操作。