@SomeBottle 在 Leetcode每日一题 —— 3464. 正方形上的点之间的最大距离 中发帖
力扣我真得控制你了 😇,这题做红温了,到后面看了一遍题解再自己写了一遍,修修改改才做出来。
这题是 max-min 优化问题,综合考察了二分思想。看来力扣算法题中的 min-max 和 max-min 问题都可以先考虑一下二分…
思路
1. 题目条件观察
题目需要从点序列中选出一个长度为 k 的子序列,使得这个序列中 \min(任意两点间的曼哈顿距离) 最大化。
最开始真有点难以下手,看到提示才发现可以去二分找最终的结果,但是如果用二分,这个结果的上下界是多少呢?
1.1. 结果下界
因为题目给的是离散的坐标点,分布在正方形边上,所以最小的两点间曼哈顿距离显然是 1。
1.2. 结果上界
这个看到题目输入数据范围说明才能知道是什么样的,题目限定选择的点数量 k >= 4,分类讨论一下:
k=4 时,整个正方形周长是 side*4,可以证明无论我怎么放四个点,必然有两点间...