目录
703. 数据流中的第 K 大元素
思路
题目解析：
数据流：
数据流和数组的区别：
代码实现
小顶堆类
测试类
力扣
我想成为一个强大、坦荡又热血的人，我爱霓虹闪烁，也爱高山流水，更爱我自己
—— 24.10.13
703. 数据流中的第 K 大元素
设计一个找到数据流中第
k大元素的类（class）。注意是排序后的第k大元素，不是第k个不同的元素。请实现
KthLargest类：
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。示例 1：
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]输出：[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // 返回 4
kthLargest.add(5); // 返回 5
kthLargest.add(10); // 返回 5
kthLargest.add(9); // 返回 8
kthLargest.add(4); // 返回 8示例 2：
输入：
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]输出：[null, 7, 7, 7, 8]
解释：
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // 返回 7
kthLargest.add(10); // 返回 7
kthLargest.add(9); // 返回 7
kthLargest.add(9); // 返回 8
思路
题目解析：
题目要求实现KthLargest类，参数列表要求传入一个整数k，代表要查找的由高到低的顺序排列，add方法，要求传入一个整数，将这个整数加入到原先数组中，按照顺序排列，当数据流有新的元素的时候，重新按升序排序数组，倒数第k个元素就是第k大的数，再从加入元素后并已排序的数组中找到倒数第k个元素，将倒数第k个元素返回
数据流：
在编程中，数据流指的是一系列连续的数据元素在系统中流动和处理的概念，本题中的数据流由整型数组实现
数据流和数组的区别：
数据流的数据是变化的，意味着有可能有更多的元素添加进来，数组是固定的
代码实现
小顶堆类
import java.util.Arrays;public class MinHeap {int[] heapArray;int size;public MinHeap(int capacity) {heapArray = new int[capacity];}public MinHeap(int[] Array) {heapArray = new int[Array.length];System.arraycopy(Array, 0, heapArray, 0, Array.length);size = Array.length;buildHeap();}private void buildHeap() {for (int i = size / 2 - 1; i >= 0; i--) {heapifyDown(i);}}public void heapifyDown(int index) {int leftChildIndex = 2 * index + 1;int rightChildIndex = leftChildIndex + 1;int SmallIndex = index;if (leftChildIndex < size && heapArray[leftChildIndex] < heapArray[SmallIndex]) {SmallIndex = leftChildIndex;}if (rightChildIndex < size && heapArray[rightChildIndex] < heapArray[SmallIndex]) {SmallIndex = rightChildIndex;}if (SmallIndex!= index) {swap(index, SmallIndex);heapifyDown(SmallIndex);}}public void swap(int i, int j) {int temp = heapArray[i];heapArray[i] = heapArray[j];heapArray[j] = temp;}public int peek() {if (size == 0) {return -1;}return heapArray[0];}public int poll() {if (size == 0) {return -1;}int maxValue = heapArray[0];heapArray[0] = heapArray[size - 1];size--;heapifyDown(0);return maxValue;}public int poll(int index) {if (size == 0 || index >= size) {return -1;}int removedValue = heapArray[index];heapArray[index] = heapArray[size - 1];size--;heapifyDown(index);return removedValue;}public void replace(int newValue) {if (size == 0) {return;}heapArray[0] = newValue;heapifyDown(0);}public boolean offer(int value) {if (size == heapArray.length) {return false;}heapArray[size] = value;heapifyUp(size);size++;return true;}private void heapifyUp(int index) {int parentIndex = (index - 1) / 2;while (index > 0 && heapArray[index] < heapArray[parentIndex]) {swap(index, parentIndex);index = parentIndex;parentIndex = (index - 1) / 2;}}public boolean isFull(){return size == heapArray.length;}public static void main(String[] args) {int[] Arr = {1, 2, 3, 4, 5, 6, 7};MinHeap maxHeap = new MinHeap(Arr);System.out.println(Arrays.toString(maxHeap.heapArray));// [7, 5, 6, 4, 2, 1, 3]maxHeap.replace(5);System.out.println(Arrays.toString(maxHeap.heapArray));// [6, 5, 5, 4, 2, 1, 3]maxHeap.poll(2);System.out.println(Arrays.toString(maxHeap.heapArray));// [6, 5, 3, 4, 2, 1, 3]System.out.println(maxHeap.peek());// 6maxHeap.poll();System.out.println(Arrays.toString(maxHeap.heapArray));// [5, 4, 3, 1, 2, 1, 3]System.out.println(maxHeap.offer(5));// trueSystem.out.println(Arrays.toString(maxHeap.heapArray));// [5, 4, 5, 1, 2, 3, 3]maxHeap.poll();System.out.println(Arrays.toString(maxHeap.heapArray));// [5, 4, 3, 1, 2, 3, 3]maxHeap.offer(9);System.out.println(Arrays.toString(maxHeap.heapArray));// [9, 4, 5, 1, 2, 3, 3]}
}测试类
public class LeetCode703MaxInDataStream {private MinHeap heap;// 在数组之中寻找第k大的元素public LeetCode703MaxInDataStream(int k,int[] nums) {heap = new MinHeap(k);for (int num : nums) {add(num);}}// 不断调用，模拟数据流中新传来的元素public int add(int val){if (!heap.isFull()){heap.offer(val);}else if(val > heap.peek()){heap.replace(val);}return heap.peek();}public static void main(String[] args) {LeetCode703MaxInDataStream test = new LeetCode703MaxInDataStream(3,new int[]{5,7,9,6,4});// 小顶堆，4 5 8 留下最大的k个就行System.out.println(test.add(11));System.out.println(test.add(7));System.out.println(test.add(9));System.out.println(test.add(6));System.out.println(test.add(4));}
}
力扣
import java.util.Arrays;public class MinHeap {int[] heapArray;int size;public MinHeap(int capacity) {heapArray = new int[capacity];}public MinHeap(int[] Array) {heapArray = new int[Array.length];System.arraycopy(Array, 0, heapArray, 0, Array.length);size = Array.length;buildHeap();}private void buildHeap() {for (int i = size / 2 - 1; i >= 0; i--) {heapifyDown(i);}}public void heapifyDown(int index) {int leftChildIndex = 2 * index + 1;int rightChildIndex = leftChildIndex + 1;int SmallIndex = index;if (leftChildIndex < size && heapArray[leftChildIndex] < heapArray[SmallIndex]) {SmallIndex = leftChildIndex;}if (rightChildIndex < size && heapArray[rightChildIndex] < heapArray[SmallIndex]) {SmallIndex = rightChildIndex;}if (SmallIndex!= index) {swap(index, SmallIndex);heapifyDown(SmallIndex);}}public void swap(int i, int j) {int temp = heapArray[i];heapArray[i] = heapArray[j];heapArray[j] = temp;}public int peek() {if (size == 0) {return -1;}return heapArray[0];}public int poll() {if (size == 0) {return -1;}int maxValue = heapArray[0];heapArray[0] = heapArray[size - 1];size--;heapifyDown(0);return maxValue;}public int poll(int index) {if (size == 0 || index >= size) {return -1;}int removedValue = heapArray[index];heapArray[index] = heapArray[size - 1];size--;heapifyDown(index);return removedValue;}public void replace(int newValue) {if (size == 0) {return;}heapArray[0] = newValue;heapifyDown(0);}public boolean offer(int value) {if (size == heapArray.length) {return false;}heapArray[size] = value;heapifyUp(size);size++;return true;}private void heapifyUp(int index) {int parentIndex = (index - 1) / 2;while (index > 0 && heapArray[index] < heapArray[parentIndex]) {swap(index, parentIndex);index = parentIndex;parentIndex = (index - 1) / 2;}}public boolean isFull(){return size == heapArray.length;}public static void main(String[] args) {int[] Arr = {1, 2, 3, 4, 5, 6, 7};MinHeap maxHeap = new MinHeap(Arr);System.out.println(Arrays.toString(maxHeap.heapArray));// [7, 5, 6, 4, 2, 1, 3]maxHeap.replace(5);System.out.println(Arrays.toString(maxHeap.heapArray));// [6, 5, 5, 4, 2, 1, 3]maxHeap.poll(2);System.out.println(Arrays.toString(maxHeap.heapArray));// [6, 5, 3, 4, 2, 1, 3]System.out.println(maxHeap.peek());// 6maxHeap.poll();System.out.println(Arrays.toString(maxHeap.heapArray));// [5, 4, 3, 1, 2, 1, 3]System.out.println(maxHeap.offer(5));// trueSystem.out.println(Arrays.toString(maxHeap.heapArray));// [5, 4, 5, 1, 2, 3, 3]maxHeap.poll();System.out.println(Arrays.toString(maxHeap.heapArray));// [5, 4, 3, 1, 2, 3, 3]maxHeap.offer(9);System.out.println(Arrays.toString(maxHeap.heapArray));// [9, 4, 5, 1, 2, 3, 3]}
}class KthLargest {private MinHeap heap;// 在数组之中寻找第k大的元素public KthLargest(int k,int[] nums) {heap = new MinHeap(k);for (int num : nums) {add(num);}}// 不断调用，模拟数据流中新传来的元素public int add(int val){if (!heap.isFull()){heap.offer(val);}else if(val > heap.peek()){heap.replace(val);}return heap.peek();}
}/*** Your KthLargest object will be instantiated and called as such:* KthLargest obj = new KthLargest(k, nums);* int param_1 = obj.add(val);*/