力扣 407 接雨水2

题目可以自己去力扣看。

  1. /**
  2.  * @param {number[][]} heightMap
  3.  * @return {number}
  4.  */
  5. var trapRainWater = function (heightMap) {
  6.     if (heightMap.length <= 2 || heightMap[0].length <= 2) {
  7.         return 0;
  8.     }
  9.     const n = heightMap.length
  10.     const m = heightMap[0].length
  11.     let vis = {}
  12.     let queue = new PriorityQueue()
  13.     let res = 0
  14.     // 把边缘点加入优先队列
  15.     for (let i = 0; i < n; i++) {
  16.         vis[i + ',' + 0] = true;
  17.         queue.add([heightMap[i][0], i, 0])
  18.         vis[i + ',' + (m - 1)] = true;
  19.         queue.add([heightMap[i][m - 1], i, m - 1])
  20.     }
  21.     for (let i = 1; i < m - 1; i++) {
  22.         vis[0 + ',' + i] = true;
  23.         queue.add([heightMap[0][i], 0, i])
  24.         vis[(n - 1) + ',' + i] = true;
  25.         queue.add([heightMap[n - 1][i], n - 1, i])
  26.     }
  27.     // 不断更新接水点
  28.     while (queue.size()) {
  29.         let [height, curN, curM] = queue.delete()
  30.         // 访问相邻点
  31.         let x = curN
  32.         let y = curM + 1
  33.         if (y < m) {
  34.             updateNode(x, y, height)
  35.         }
  36.         y = curM - 1
  37.         if (y >= 0) {
  38.             updateNode(x, y, height)
  39.         }
  40.         y = curM
  41.         x = curN - 1
  42.         if (x >= 0) {
  43.             updateNode(x, y, height)
  44.         }
  45.         x = curN + 1
  46.         if (x < n) {
  47.             updateNode(x, y, height)
  48.         }
  49.     }
  50.     return res;
  52.     // 更新节点信息，如果没访问过就把节点推入优先队列
  53.     function updateNode(x, y, height) {
  54.         if (!vis[x + ',' + y]) {
  55.             vis[x + ',' + y] = true
  56.             if (heightMap[x][y] < height) {
  57.                 res += (height - heightMap[x][y])
  58.             }
  59.             queue.add([Math.max(height, heightMap[x][y]), x, y])
  60.         }
  61.     }
  63. };
  65. // 优先队列
  66. class PriorityQueue {
  67.     constructor() {
  68.         this.arr = [];
  69.     }
  70.     shiftMinUp() { // 自底向上调整
  71.         const { arr } = this;
  72.         let i = arr.length - 1;
  73.         let j = ~~((i + 1) / 2) - 1;
  74.         let temp = arr[i];
  75.         while (j >= 0) {
  76.             if (temp[0] < arr[j][0]) {
  77.                 arr[i] = arr[j];
  78.             } else {
  79.                 break;
  80.             }
  81.             i = j;
  82.             j = j = ~~((j + 1) / 2) - 1;
  83.         }
  84.         arr[i] = temp;
  85.     }
  86.     shiftDownMin() { // 自顶向下调整
  87.         const { arr } = this;
  88.         if (!arr.length) {
  89.             return arr;
  90.         }
  91.         let i = 0;
  92.         let j = 2 * i + 1;
  93.         let temp = arr[0];
  94.         while (j < arr.length) {
  95.             if (j < arr.length - 1 && arr[j][0] > arr[j + 1][0]) {
  96.                 j++;
  97.             }
  98.             if (temp[0] > arr[j][0]) {
  99.                 arr[i] = arr[j];
  100.             } else {
  101.                 break;
  102.             }
  103.             i = j;
  104.             j = j * 2 + 1;
  105.         }
  106.         arr[i] = temp;
  107.     }
  108.     add(num) { // 插入元素的时候在数组最后，也就是在叶子节点，需要往上调整位置
  109.         const { arr } = this;
  110.         arr.push(num);
  111.         this.shiftMinUp();
  112.     }
  113.     delete() { // 删除时把队尾放到队首，此时可以从上到下调整位置
  114.         const { arr } = this;
  115.         let d = arr[0];
  116.         arr[0] = arr[arr.length - 1];
  117.         arr.pop()
  118.         this.shiftDownMin();
  119.         return d;
  120.     }
  121.     size() {
  122.         return this.arr.length;
  123.     }
  124.     get() {
  125.         return this.arr[0];
  126.     }
  127. }