LeetCode день 237–1765

Кожен день має одне випадкове завдання з leetcode. Сьогоднішнє завдання — 1765. Карта найвищої вершини

Опис:

Вам надано ціле матрицю isWater розміру m x n, що представляє карту землі та води.

• Якщо isWater[i][j] == 0, клітина (i, j) є землею.
• Якщо isWater[i][j] == 1, клітина (i, j) є водою.

Необхідно призначити кожній клітині висоту таким чином, щоб дотримувалися наступні правила:

• Висота кожної клітини повинна бути невід'ємною.
• Якщо клітина є водою, її висота повинна бути 0.
• Будь-які дві сусідні клітини повинні мати абсолютну різницю висот не більше 1. Клітина є сусідом іншої, якщо вона розташована безпосередньо на півночі, сході, півдні або заході від іншої (тобто їхні сторони торкаються).

Знайдіть розподіл висот, так щоб максимальна висота в матриці була максимальною.

Поверніть ціле число в матриці height розміру m x n, де height[i][j] це висота клітини (i, j). Якщо є кілька рішень, поверніть будь-яке з них.

Приклад 1:

Вхід: isWater = [[0,1],[0,0]]  
Вихід: [[1,0],[2,1]]  
Пояснення: Зображення показує призначені висоти для кожної клітини.  
Блакитна клітина — це водяна клітина, а зелені клітини — це земельні клітини.

Приклад 2:

Вхід: isWater = [[0,0,1],[1,0,0],[0,0,0]]  
Вихід: [[1,1,0],[0,1,1],[1,2,2]]  
Пояснення: Висота 2 — це максимальна можлива висота для будь-якого призначення.  
Будь-яке призначення висоти, яке має максимальну висоту 2, при дотриманні всіх правил, також буде прийнято.

Ми створюємо масив ans, заповнюємо всі клітини значенням -1. Встановлюємо ці водяні клітини як 0 і зберігаємо їхні [r, c] у queue.

Починаємо з цих водяних клітин. Усі сусідні клітини повинні збільшуватися на 1, якщо вони ще не використані (тобто все ще мають значення -1). Зберігаємо ці збільшені клітини в queue. Перевіряємо всю чергу до кінця.

В кінці повертаємо ans як відповідь.

Якщо довжина isWater дорівнює nm, часова складність — O(nm)

/**  
 * @param {number[][]} isWater  
 * @return {number[][]}  
 */  
var highestPeak = function (isWater) {  
 const direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]  
 const n = isWater.length  
 const m = isWater[0].length  
 const ans = Array.from({ length: n }, () => Array(m).fill(-1))  
 const queue = []  

 for (let r = 0; r < n; r++) {  
 for (let c = 0; c < m; c++) {  
 if (isWater[r][c] === 1) {  
 ans[r][c] = 0  
 queue.push([r, c])  
 }  
 }  
 }  

 let index = 0  
 while (index < queue.length) {  
 const [r, c] = queue[index]  
 index++  

 for (const [x, y] of direction) {  
 const newX = r + x  
 const newY = c + y  
 if (newX >= 0 && newX < n && newY >= 0 && newY < m && ans[newX][newY] === -1) {  
 ans[newX][newY] = ans[r][c] + 1  
 queue.push([newX, newY])  
 }  
 }  
 }  


 return ans  
};




Перекладено з: [LeetCode day237–1765](https://medium.com/@okesseko/leetcode-day237-1765-ce204e1ea8cb)