PHP中如何找到数据流中的第K个最大元素？

本文共计783个文字，预计阅读时间需要4分钟。

利用最小堆的性质，最小堆的根节点一定是所有节点中最小的。因此，我们只需要维护一个包含K个元素的最小堆即可。只要新元素的值大于最小堆的根节点值，就移除根节点，并将新元素插入堆中。这样，堆顶始终是当前最小的K个元素中的一个。

利用最小堆的性质，该最小堆的根结点一定是所有结点中最小的。所以，我们只需要维护K个元素大小的最小堆。只要是大于最小堆的根结点的值，就移除该根结点的值，把该值插入最小堆中。

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例：

int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8

说明: 你可以假设 nums 的长度≥ k-1 且k ≥ 1。