今日头条2018 坐标

今日头条2018 坐标

今日头条2018 坐标

今日头条2018 坐标

其中“最大”是在右上方的意思,即任意一点没有同时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相同的情况下,不认为是右上角有点的。

今日头条2018 坐标


按照上述方法进行操作,顺序为E、D、C、B、A


正解:x从小到大排序,在x相等的情况下,y从大到小排序。

时间复杂度O(n*log(n))

A D C B E

排除了x相等的情况下,y值不同的干扰情况。