mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
49 lines
2.2 KiB
HTML
49 lines
2.2 KiB
HTML
<p>You are given an array <code>points</code> representing integer coordinates of some points on a 2D plane, where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>.</p>
|
|
|
|
<p>The distance between two points is defined as their <span data-keyword="manhattan-distance">Manhattan distance</span>.</p>
|
|
|
|
<p>Return <em>the <strong>minimum</strong> possible value for <strong>maximum</strong> distance between any two points by removing exactly one point</em>.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">points = [[3,10],[5,15],[10,2],[4,4]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">12</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>The maximum distance after removing each point is the following:</p>
|
|
|
|
<ul>
|
|
<li>After removing the 0<sup>th</sup> point the maximum distance is between points (5, 15) and (10, 2), which is <code>|5 - 10| + |15 - 2| = 18</code>.</li>
|
|
<li>After removing the 1<sup>st</sup> point the maximum distance is between points (3, 10) and (10, 2), which is <code>|3 - 10| + |10 - 2| = 15</code>.</li>
|
|
<li>After removing the 2<sup>nd</sup> point the maximum distance is between points (5, 15) and (4, 4), which is <code>|5 - 4| + |15 - 4| = 12</code>.</li>
|
|
<li>After removing the 3<sup>rd</sup> point the maximum distance is between points (5, 15) and (10, 2), which is <code>|5 - 10| + |15 - 2| = 18</code>.</li>
|
|
</ul>
|
|
|
|
<p>12 is the minimum possible maximum distance between any two points after removing exactly one point.</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">points = [[1,1],[1,1],[1,1]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">0</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>Removing any of the points results in the maximum distance between any two points of 0.</p>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>3 <= points.length <= 10<sup>5</sup></code></li>
|
|
<li><code>points[i].length == 2</code></li>
|
|
<li><code>1 <= points[i][0], points[i][1] <= 10<sup>8</sup></code></li>
|
|
</ul>
|