今日头条2018 坐标
![Image 1][]
其中“最大”是在右上方的意思,即任意一点没有同时x,y都比它大的点。
创建Node节点
class Node{
int x;
int y;
}
将节点按横坐标排序,之后从后向前查找,记录yMax。
如果当前点的y坐标大于yMax,则当前点为符合题意的点。
或者 预处理数组
x 0 1 2 3 4 5
y 3 6 7 2 5 4
a 7 7 7 5 5 4
a是从右边向左生成的,代表从i开始到最右方向y的最大值。
变形题目:x不同y相同的情况下,不认为是右上角有点的。
![Image 1][]
按照上述方法进行操作,顺序为E、D、C、B、A
正解:x从小到大排序,在x相等的情况下,y从大到小排序。
时间复杂度O(n*log(n))
A D C B E
排除了x相等的情况下,y值不同的干扰情况。
[Image 1]:
还没有评论,来说两句吧...