373.Find K Pairs with Smallest Sums 给定两个已升序排列数组nums1、nums2与数字k,返回k个和最小的pair(nums1[i],nums2[j]) Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6]
分析:该题目除了暴力破解,乍一看思路放在找到当前和最小的对后,在元素附近找,但是怎么想也没有得出所以然。看了下forum中讨论,将两个数组分别作为行列,对应的和作为二维数组,那么这道题就立即转化为378.Kth Smallest Element in a Sorted Matrix。
var trapRainWater = function (heightMap) { if (!heightMap || heightMap.length < 1 || heightMap[0].length < 1) return0; //build min heap with the four borders var row = heightMap.length, col = heightMap[0].length; var used = []; for (i = 0; i < row; i++) { used.push(newArray(col).fill(false)); } //heap element (i,j,height) var minHeap = newHeap(function (x) { return x[2]; }); for (var i = 0; i < row; i++) { minHeap.push([i, 0, heightMap[i][0]]); minHeap.push([i, col - 1, heightMap[i][col - 1]]); used[i][0] = used[i][col - 1] = true; } for (i = 1; i < col - 1; i++) { minHeap.push([0, i, heightMap[0][i]]); minHeap.push([row - 1, i, heightMap[row - 1][i]]); used[0][i] = used[row - 1][i] = true; } //iterate from border to center var res = 0, moves = [[-1, 0], [1, 0], [0, -1], [0, 1]]; for (i = 0; i < row; i++) { for (var j = 0; j < col; j++) { var minHeight = minHeap.pop(); for (var k = 0; k < moves.length; k++) { var x = minHeight[0] + moves[k][0], y = minHeight[1] + moves[k][1]; if (x > -1 && x < row && y > -1 && y < col && !used[x][y]) { if (minHeight[2] > heightMap[x][y]) { res += minHeight[2] - heightMap[x][y]; minHeap.push([x, y, minHeight[2]]); } else { minHeap.push([x, y, heightMap[x][y]]); } used[x][y] = true; } } } } return res; };