On a plane there are n
points with integer coordinates points[i] = [xi, yi]
. Your task is to find the minimum time in seconds to visit all points.
You can move according to the next rules:
- In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
- You have to visit the points in the same order as they appear in the array.
Example 1:
Input: points = [[1,1],[3,4],[-1,0]] Output: 7 Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0] Time from [1,1] to [3,4] = 3 seconds Time from [3,4] to [-1,0] = 4 seconds Total time = 7 seconds
Example 2:
Input: points = [[3,2],[-2,2]] Output: 5
Constraints:
points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000
Solution: Geometry + Greedy
dx = abs(x1 – x2)
dy = abs(y1 – y2)
go diagonally first for min(dx, dy) steps, and then go straight line for abs(dx – dy) steps.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: int minTimeToVisitAllPoints(vector<vector<int>>& points) { int ans = 0; for (size_t i = 1; i < points.size(); ++i) { int dx = abs(points[i - 1][0] - points[i][0]); int dy = abs(points[i - 1][1] - points[i][1]); ans += min(dx, dy) + abs(dx - dy); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment