378 有序矩阵中第k小的元素

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。

你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

public int kthSmallest(int[][] matrix, int k) {
        if (k < 0 || k > matrix.length * matrix[0].length) {
            return -1;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (maxHeap.size() < k) {
                    maxHeap.offer(matrix[i][j]);
                } else {
                    if (maxHeap.peek() > matrix[i][j]) {
                        maxHeap.poll();
                        maxHeap.offer(matrix[i][j]);
                    }
                }
            }
        }
        return maxHeap.peek();
    }

维护一个最大堆，大小为k，即maxHeap.poll()为第k小的元素