3815. Design Auction System

📘 題目敘述

你要設計一個即時拍賣系統，用來管理多位使用者對多個商品的出價。

每一筆出價都包含：

• userId
• itemId
• bidAmount

請實作 AuctionSystem 類別，支援以下操作：

• AuctionSystem()：初始化拍賣系統
• addBid(int userId, int itemId, int bidAmount)：
  • 新增一筆使用者 userId 對商品 itemId 的出價 bidAmount。
  • 若同一個 userId 已經對該 itemId 出價過，則用新的 bidAmount 覆蓋原本出價。
• updateBid(int userId, int itemId, int newAmount)：
  • 更新 userId 對 itemId 的既有出價為 newAmount。（題目保證這筆出價存在）
• removeBid(int userId, int itemId)：
  • 移除 userId 對 itemId 的出價。（題目保證這筆出價存在）
• getHighestBidder(int itemId)：
  • 回傳 itemId 當前最高出價者的 userId。
  • 若最高出價金額相同，回傳 userId 較大的那位。
  • 若該商品沒有任何出價，回傳 -1。

條件限制

• 1 <= userId, itemId <= 5 * 10^4
• 1 <= bidAmount, newAmount <= 10^9
• addBid / updateBid / removeBid / getHighestBidder 總呼叫次數最多 5 * 10^4
• 題目保證 updateBid 與 removeBid 的操作一定是有效出價

🧠 解題思路（但最後TLE）

我的做法是把每個 itemId 的出價記錄分開存，並且用「兩個 vector 對齊」的方式保存出價資料：

• users[itemId]：存所有對該商品出價的 userId
• bids[itemId]：存對應的出價金額，並且和 users[itemId] 用同一個索引對齊

所以對同一個 itemId 來說：

• users[itemId][k] 的出價金額就是 bids[itemId][k]

接下來每個操作都只要在該商品的 vector 裡做線性掃描即可。

所有變數

• users：二維 vector，users[itemId] 存該商品所有出價者的 userId
• bids：二維 vector，bids[itemId] 存該商品所有出價金額（索引和 users 對齊）
• hprice：在 getHighestBidder 中，當前找到的最高出價金額
• buser：在 getHighestBidder 中，對應最高出價者的 userId
• u：掃描某個 itemId 時取出的使用者 id
• a：掃描某個 itemId 時取出的出價金額
• i：掃描 users[itemId] / bids[itemId] 的索引

🪜 主要流程步驟

1. 建構子：初始化

• 我用 assign(50001, {}) 先建立 itemId = 0~50000 的容器
• 讓每個 itemId 都有自己的出價列表（一開始是空的）
• 之後存取 users[itemId] / bids[itemId] 都不會越界

2. addBid(userId, itemId, bidAmount)：新增 / 覆蓋出價

我分兩種情況處理：

情況一：同一個 userId 已經出價過

• 線性掃描 users[itemId]
• 若找到 users[itemId][i] == userId
  • 直接覆蓋 bids[itemId][i] = bidAmount
  • 然後 return

情況二：userId 第一次對此 itemId 出價

• 把 userId 加到 users[itemId]
• 把 bidAmount 加到 bids[itemId]
• 兩個 vector 的索引保持對齊

3. updateBid(userId, itemId, newAmount)：更新既有出價

• 題目保證這筆出價一定存在
• 所以我直接線性掃描 users[itemId]
• 找到對應 userId 後，把 bids[itemId][i] 改成 newAmount，然後 return

4. removeBid(userId, itemId)：移除出價

• 題目保證這筆出價一定存在
• 我線性掃描 users[itemId] 找到 userId 的位置 i
• 一旦找到：
  • users[itemId].erase(users[itemId].begin() + i)
  • bids[itemId].erase(bids[itemId].begin() + i)
• 這樣可以確保兩個 vector 仍然索引對齊

5. getHighestBidder(itemId)：找最高出價者

情況一：該商品沒有任何出價

• users[itemId].empty() → 回傳 -1

情況二：有出價

• 線性掃描所有出價 (userId, bidAmount)
• 若出價金額 a 比目前 hprice 大 → 更新 (hprice, buser)
• 若出價金額相同 a == hprice
  • 題目規定要回傳 userId 較大的
  • 所以若 u > buser → 更新 buser

最後回傳 buser。

💻 程式碼實作

class AuctionSystem {
public:
    vector<vector<int>> users;
    vector<vector<int>> bids;

    AuctionSystem() {
        users.assign(50001, {});
        bids.assign(50001, {});
    }

    void addBid(int userId, int itemId, int bidAmount) {
        for (int i = 0; i < (int)users[itemId].size(); i++) {
            if (users[itemId][i] == userId) {
                bids[itemId][i] = bidAmount;
                return;
            }
        }
        users[itemId].push_back(userId);
        bids[itemId].push_back(bidAmount);
    }

    void updateBid(int userId, int itemId, int newAmount) {
        for (int i = 0; i < (int)users[itemId].size(); i++) {
            if (users[itemId][i] == userId) {
                bids[itemId][i] = newAmount;
                return;
            }
        }
    }

    void removeBid(int userId, int itemId) {
        for (int i = 0; i < (int)users[itemId].size(); i++) {
            if (users[itemId][i] == userId) {
                users[itemId].erase(users[itemId].begin() + i);
                bids[itemId].erase(bids[itemId].begin() + i);
                return;
            }
        }
    }

    int getHighestBidder(int itemId) {
        if (users[itemId].empty()) {
            return -1;
        }
        int hprice = -1;
        int buser = -1;
        for (int i = 0; i < (int)users[itemId].size(); i++) {
            int u = users[itemId][i];
            int a = bids[itemId][i];
            if (a > hprice || (a == hprice && u > buser)) {
                hprice = a;
                buser = u;
            }
        }
        return buser;
    }
};

🔗 題目連結

https://leetcode.com/problems/design-auction-system/