這題是設計一個資料結構，來動態地保持一組資料的第 K 大元素。這是典型的資料流問題，尤其適合使用堆來進行處理。

題目：

給定一個整數陣列 nums 和一個整數 k，設計一個 KthLargest 類別，當插入一個新的數字時，能夠回傳資料流中第 K 大的元素。

範例：

輸入: 
k = 3, nums = [4, 5, 8, 2]
KthLargest kthLargest = new KthLargest(3, nums);
kthLargest.add(3);   // 回傳 4
kthLargest.add(5);   // 回傳 5
kthLargest.add(10);  // 回傳 5
kthLargest.add(9);   // 回傳 8
kthLargest.add(4);   // 回傳 8

解題思路

先用最直覺的方式實做出來，add 後再針對陣列元素做排序，然後再回傳第k大的元素，

class KthLargest {
public:
    KthLargest(int k, vector<int>& nums) {
        mK = k;
        mNums = nums;
    }
    
    int add(int val) {
        mNums.push_back(val);
        sort(mNums.begin(), mNums.end(), std::greater<int>());
        return mNums[mK-1];
    }
private:
    int mK;
    vector<int> mNums;
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

送出後結果是 Time Limit Exceeded 超時，

改用最小堆 min heap (Priority Queue)，最 top 為最小，然後這個堆維持只有 k 個元素，這樣堆的 top 就會是第 k 大的元素，這樣 add 的時間會縮短，不用對原本整個陣列再排序，PriorityQueue 就是插入到最後一個，然後在做上升的動作，

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

後來發現可以將重複邏輯減少，例如在 KthLargest 建構時就用 add() 將每個元素加入 min heap 中，

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

參考：
#703. Kth Largest Element in a Stream