Back to Leetcode

Readme

Greedy/3027.Find-the-Number-of-Ways-to-Place-People-II/Readme.md

latest910 B
Original Source

3027.Find-the-Number-of-Ways-to-Place-People-II

此题允许n^2的时间复杂度,可以暴力枚举所有符合条件的{左上角、右下角}配对,判断是否是合法的解。

对于二维坐标的点,有两个方向上的自由度,同时考虑他们之间的包含关系肯定复杂,我们必然会尝试将他们先按照一个维度排序,比如说x轴。对于两个点A和B在x轴上是递增的,他们能够配对成功的条件就是:x轴上A与B之间的点,不能在y轴上也出现在A与B之间。换句话说,如果横坐标位于A与B之间的所有点的y坐标上限是P(排除那些高于A的点),那么B能与A配对的条件就是:B的y周坐标必须大于P。随着B在x轴上离A越远,那么这个上限值其实是单调递增的。由此从左到右扫一遍所有的点,不断更新上限P,就能判断出每个点是否可以与A配对。