【优先队列】378. 有序矩阵中第 K 小的元素

378. 有序矩阵中第 K 小的元素

解题思路

• 初始化最大堆： 创建一个最大堆的优先队列，这使得队列中的元素按照降序排列。

• 遍历矩阵并更新队列： 通过嵌套的循环遍历二维矩阵中的每一个元素，将元素添加到最大堆中。

• 控制队列大小： 在添加元素后，检查队列的大小是否已经达到了k。如果已经达到，而且当前遍历到的元素大于队列中最大的元素，就可以提前结束遍历。因为矩阵是按行和列有序的，一旦超过第k小的元素，后面的元素肯定更大。同时，如果队列的大小超过了k，就从队列中移除最大的元素，以保持队列中仅有k个最小的元素。

• 返回结果： 最终返回最大堆中的最大元素，这就是矩阵中第k小的元素。

class Solution {public int kthSmallest(int[][] matrix, int k) {// 使用优先队列保留K个最小的元素// 使用最大堆那么队列的元素都是降序排列 最大的元素在队头PriorityQueue<Integer> MaxPQ = new PriorityQueue<>(Collections.reverseOrder());for(int[] row:matrix){for(int num: row){// 如果队列已经满了 并且当前的元素大于队列中的最大元素 也就是队头第k小元素if(MaxPQ.size() == k && num > MaxPQ.peek()){break;}MaxPQ.add(num);// 当前遍历的元素添加到优先队列中// 如果队列元素超过K移除队头元素if(MaxPQ.size() > k){MaxPQ.remove();}}}// 当把整个矩阵遍历完毕之后队头元素就是当前队列最大元素 也就是第k小元素return MaxPQ.remove();}}