博文中会简要介绍Leetcode P0215题目分析及解题思路。

“Kth Largest Element in an Array”是一道很经典的考察堆排序（或者说堆结构）的题目。将这道题抽象后其实就是寻找Top K的元素。我们可以通过维护一个容量为k的堆来实现解答。

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

在这道题里我们要用到的是最小堆。

为什么找第k大的元素会用到最小堆呢？

这主要和我们的解题思路有关。我们需要维护一个存放了前k大的元素的堆，此时如果想要得到第k大的元素，为了能够直接得到，我们会将这个元素放在堆顶。实际上第k大的元素在这k个元素里面最终应当是最小的那个，并且它又被放在了堆顶，所以我们要用到的应当是最小堆。

如何维护这个容量为k的最小堆呢？

具体思路如下，我们遍历给定的数组，对于数组内的每个元素，我们先判断当前最小堆内的元素个数是否小于k，如果小于k则我们直接将元素塞入最小堆；否则，我们判断当前元素和堆顶元素的大小关系，如果大于等于堆顶元素，我们将堆顶元素pop出来，塞入当前元素。最后我们最小堆的堆顶就是我们需要找的第k大的元素。

以下是Java的题解代码实现。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> minHeap = new PriorityQueue<>();
        for (int num: nums) {
            if (minHeap.size() < k)
                minHeap.offer(num);
            else {
                if (num >= minHeap.peek()) {
                    minHeap.poll();
                    minHeap.offer(num);
                }
            }
        }
        
        return minHeap.peek();
    }
    
}

以下是C++的题解代码实现。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        auto comp = [](int n1, int n2) -> bool {
            return n1 > n2;
        };
        
        priority_queue<int, vector<int>, decltype(comp)> min_heap(comp);
        for (int num: nums) {
            if (min_heap.size() < k)
                min_heap.push(num);
            else {
                if (num >= min_heap.top()) {
                    min_heap.pop();
                    min_heap.push(num);
                }
            }
        }
        
        return min_heap.top();
    }
};