【LeetCode--215】数组中的第K个最大元素----个人理解

题目

思路

主要是利用java中的优先队列来解决这个问题，因为优先队列底层就是一个最大堆或者最小堆。

这题中，是求第K个最大元素，所以我们要用最小堆来作做为数据结构。

算法思想： 先按数组顺序将K个元素加入的优先队列中，这时候优先队列的peek(）就是这K个元素中最小的那个，然后继续遍历数组，如果当前元素比堆顶的元素要大，那么就把堆顶元素poll() （也就是出队）,将当前元素入队。

我的理解： 假设数组大小为N，那么就类似N个人要竞争K个席位（K<N）。首先就按先来后到的顺序，暂时把前面K个人放入席位中。之后类似淘汰机制，让后来的人和这K个人中最弱的那个比较，如果他比最弱的那个人强，那么他就可以进入席位，而把最弱的那个人踢出去。
之后呢，因为优先队列的机制，会自动将最弱的那个人排到堆顶，于是后来的人继续和最弱的那个人比较，最终就会得到最强的K个人，而堆顶就是第K个强的人。