Easy
Related Topics: Tree / Design / BST / Heap (Priority Queue) / BT / Data Stream
LeetCode Source

解題想法

Python

在每次執行 add() 時，都透過 sort 反向排序

回傳 k-1 的 index 值

C++

如果用 Python 解法會 Time Limit Exceed

改成用 priority queue

此時使用 min Heap，並將初始的數值都放到 min Heap 中

此時 add() function 會將 val 放置合理位置

如果 k < min heap 的 size 時

則把 val push 到 min heap

如果 min heap 的 top 比 val 大

則將 top pop 出，並將 val push 至 min heap

add function 回傳 min heap 的 top 值

Complexity

Time Complexity: O(1)
Space Complexity: O(n)

Python

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.index = k-1
        self.bag = nums

    def add(self, val: int) -> int:
        self.bag.append(val)
        self.bag.sort(reverse=True)
        return self.bag[self.index]

C++

class KthLargest {
private:
    int aa;
    std::priority_queue<int, vector<int>, std::greater<int>> minHeap;
public:
    KthLargest(int k, vector<int>& nums) : aa(k) {
        for (int n : nums)
            add(n);
    }
    
    int add(int val) {
        if (minHeap.size() < aa)
            minHeap.push(val);
        else if (val > minHeap.top()) {
            minHeap.pop();
            minHeap.push(val);
        }
        return minHeap.top();
    }
};