📘 題目敘述
給你一個整數陣列 nums 和一個整數 k，請回傳陣列中第 k 大的元素。
注意：你要找的是「排序後的第 k 大元素」，不是第 k 個不同的元素。
你能在不排序的情況下解出來嗎？
條件限制
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
🧠 解題思路
我這題用的是「大小固定為 k 的最小堆（min-heap）」。
核心想法是：
- 如果我手上永遠只保留「目前看過的元素裡最大的
k個」 - 那麼這
k個裡面最小的那個，就剛好是整體的第k大
所以我用一個 min-heap q：
- 每看到一個數字就丟進去
- 只要 heap 的大小超過
k，就把最小的那個彈掉，這代表「太小的元素不可能成為前k大」，直接丟掉就好
最後 heap 裡剩下的就是「最大的 k 個」，而 q.top() 就是第 k 大。
所有變數
q：最小堆（min-heap），用來維持「目前最大的 k 個元素」，堆頂永遠是這 k 個裡最小的那個
🪜 主要流程步驟
1. 用 min-heap 維持「最大的 k 個元素」
我宣告 priority_queue<int, vector<int>, greater<int>> q;，這樣 q.top() 會是目前 heap 裡最小的元素。
2. 逐一把 nums 的元素放進 heap
每讀到一個 nums 裡的值，我就先 q.push(i)。
3. 如果 heap 超過 k 個，就把最小的丟掉
一旦 q.size() > k，就 q.pop()。
這一步等於在做：「我只想保留最大的 k 個，其他更小的就不用留」。
4. 最後 heap 的頂端就是答案
跑完後 heap 內一定剩下 k 個元素，而且是「最大的 k 個」。因此 q.top() 就是第 k 大，直接回傳。
⏱️ 複雜度
- 時間複雜度：
O(n log k)，每個元素最多 push / pop 一次，heap 操作是log k - 空間複雜度：
O(k)，heap 最多只保留k個元素
💻 程式碼實作
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> q; // top是最小
for (int i : nums) {
q.push(i);
if (q.size() > k) {
q.pop();
}
}
return q.top();
}
};
🔗 題目連結
https://leetcode.com/problems/kth-largest-element-in-an-array/