【优先队列】378. 有序矩阵中第 K 小的元素-Toy模板网

这篇具有很好参考价值的文章主要介绍了【优先队列】378. 有序矩阵中第 K 小的元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

解题思路

初始化最大堆：创建一个最大堆的优先队列，这使得队列中的元素按照降序排列。
遍历矩阵并更新队列：通过嵌套的循环遍历二维矩阵中的每一个元素，将元素添加到最大堆中。
控制队列大小：在添加元素后，检查队列的大小是否已经达到了k。如果已经达到，而且当前遍历到的元素大于队列中最大的元素，就可以提前结束遍历。因为矩阵是按行和列有序的，一旦超过第k小的元素，后面的元素肯定更大。同时，如果队列的大小超过了k，就从队列中移除最大的元素，以保持队列中仅有k个最小的元素。
返回结果：最终返回最大堆中的最大元素，这就是矩阵中第k小的元素。文章来源地址https://www.toymoban.com/news/detail-814670.html

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();

    }
}