Условие

Дан массив points, где points[i] = [x, y] — координаты точки на 2D-плоскости. За один шаг можно передвигаться по горизонтали, вертикали или диагонали. Нужно найти минимальное количество шагов, чтобы посетить все точки по порядку.

Примеры

Input: [[1,1],[3,4],[-1,0]] Output: 7 Explanation: Один из оптимальных маршрутов: [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]. Время от [1,1] до [3,4] = 3 секунды. Время от [3,4] до [-1,0] = 4 секунды. Общее время = 7 секунд.

Input: [[3,2],[-2,2]] Output: 5

Решение

fun minTimeToVisitAllPoints(points: Array<IntArray>): Int {
    var time = 0
    
    for (i in 1 until points.size) {
        // Разница по x и y между текущей и предыдущей точкой
        val dx = kotlin.math.abs(points[i][0] - points[i - 1][0])
        val dy = kotlin.math.abs(points[i][1] - points[i - 1][1])
        
        // Минимальное количество шагов равно максимальному из двух расстояний
        time += maxOf(dx, dy)
    }
    
    return time // Возвращаем общее время перемещения
}

Временная сложность

O(n), где n — количество точек.

Пространственная сложность

O(1), так как используются только переменные.