lc373 Find K Pairs with Smallest Sums该用最大还是最小堆的问题

首先我的思路是，用最大堆，当比k个多元素的时候，就poll出去，留下的自然是最小的

这是我的代码：

[mw_shl_code=java,true]public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k){

List<List<Integer>> res= new ArrayList<>();

//corner case

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b)->b[0]+b[1]-a[0]-a[1]);



for(int nums:nums1){

maxHeap.offer(new int[]{nums,nums2[0],0});



if(maxHeap.size()>k){

maxHeap.poll();

}

}

//再倒出来

while(!maxHeap.isEmpty() && k-->0){

int [] cur=maxHeap.poll();[br]
res.add(Arrays.asList(cur[0],cur[1]));



if(cur[2]==nums2.length-1) continue;

maxHeap.offer(new int[]{cur[0],nums2[cur[2]+1], cur[2]+1});

}

return res;[/mw_shl_code]

然而，当test case 为：

[1,1,2]

[1,2,3]

2

的时候，我的结果[[1,1],[2,1]]和答案不同：[[1,1],[1,1]]

然后看到一个正确的答案代码，用的minHeap，我觉得其他代码也一样：

[mw_shl_code=java,true]public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

List<List<Integer>> res = new ArrayList<>();

if (nums1.length == 0 || nums2.length == 0 || k == 0) {

return res;

}

PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> (a[0] + a[1] - b[0] - b[1]));

for (int i = 0; i < nums1.length && i < k; i++) {

minHeap.offer(new int[]{nums1[i], nums2[0], 0});

}

while (!minHeap.isEmpty() && k-- > 0) {

int[] cur = minHeap.poll();[br]
res.add(Arrays.asList(cur[0],cur[1]));

if (cur[2] == nums2.length - 1) continue;

minHeap.offer(new int[]{cur[0], nums2[cur[2] + 1], cur[2] + 1});

}

return res;

}[/mw_shl_code]

这个运行结果就正确，不知为何

望指教