This problem a hand, feeling lofty, the first reaction is to feel very difficult, in fact, is a typical dress up as a pig eat tiger’s topic, find the right method is very simple.

Come on! Look at the topic ~

Question 1266. Minimum time to access all points

There are n points on the plane whose positions are represented by integer coordinates points[I] = [xi, yi]. Calculate the minimum time (in seconds) required to access all of these points.

You need to move on the plane according to the following rules:

For every second, you can: move 1 unit length horizontally, or 1 unit length vertically, or cross the diagonal SQRT (2) units (think of as moving 1 unit length horizontally and 1 unit length vertically in one second). These points must be accessed in the order in which they appear in the array. When accessing a point, you can pass through points that appear after that point, but those points do not count as valid access.

Example 1:

Input: points = [[1.1], [3.4], [...1.0]] output:7Explanation: An optimal access path is: [1.1] - > [2.2] - > [3.3] - > [3.4] - > [2.3] - > [1.2] - > [0.1] - > [...1.0] from [1.1] to [3.4] need3Seconds from [3.4] to [...1.0] need4It takes a second7 秒
Copy the code

Example 2:

Input: points = [[3.2], [...2.2]] output:5
Copy the code

Tip:

  • points.length == n
  • 1 <= n <= 100
  • points[i].length == 2
  • -1000 <= points[i][0], points[i][1] <= 1000

Answer key:

Let’s eat it step by step.

The first step

This problem is actually a geometric math problem, the first step of the correct solution is to draw the rectangular coordinate system, to all coordinate points on the axis draw parallel lines relative to the axis, will form a small square, and then mark the location of each point according to the example, try to take two steps, and then can discover the mystery.

The second step

On the smallest square, one unit of time is counted from one point to another adjacent point, and the diagonal of the smallest square is also a unit of time. There are only two positions of two points in the coordinate system: on a line (including similarities) and on a rectangular diagonal, which is divided into squares and rectangles.

The third step

If you’re on a line, how do you calculate this distance? It’s the length of the line segment; Mathematically, it’s the absolute value of the difference; On the diagonal of the square, since the smallest square diagonal is a unit length, this time value can also be measured by the length of the sides, which is the absolute value of the difference between the xy values on either axis; On the rectangle diagonal, the algorithm of this time value can first walk the largest square in the rectangle, and then walk the rest of the line; You’ll notice that the length of the largest square in a rectangle is the length of the shortest side of the rectangle, so the point that goes on the diagonal can be summed up as the longest side;

The fourth step

According to the above analysis, the time value for walking through two points in all cases can be summarized as the longest side length of the rectangle formed between two points (a line can assume that one side is 0). You go through all the points in this way, and then you add up each section to get the final result.

Finally, the answer:

var minTimeToVisitAllPoints = function(points) {
  let res = 0
  for(let i = 0; i < points.length-1; i++){
    let next = points[i + 1]
    let cur = points[i]
    let diff = Math.max(Math.abs(cur[0] - next[0]), Math.abs(cur[1] - next[1]))
    res += diff
  }
  return res
}
Copy the code

This solution can also be optimized to reduce the calculation of length -1 of points by one step per cycle, which can save some time

var minTimeToVisitAllPoints = function(points) {
  let res = 0
  for(let i = 1; i < points.length; i++){
    let last = points[i - 1]
    let cur = points[i]
    let diff = Math.max(Math.abs(cur[0] - last[0]), Math.abs(cur[1] - last[1]))
    res += diff
  }
  return res
}
Copy the code

The complexity of the

Time complexity O(n), where NN is the length of the array. ; Space complexity O(1);

Title link: leetcode-cn.com/problems/mi…