leetcode 853. 车队

题目链接
思路：排序+栈
分析：上来读完题，很容易发现这就是很多根直线，那么在二维坐标系中画画图。

x轴是时间，y轴是位置
如果要相遇，必定是上图这种情况。
位置高的，耗时比位置低的长。
并且相遇后，图将变成如下这种。

那么其实下面更低的位置出发的车，如果要和上面的相交，那么不用去管那根绿线了，只需要看是否和那个橙线是否相交。
是否有人产生疑问，就是是不是 存在位置在下面 和绿色线 相交 但是不和橙色相交的线呢？
这种线条肯定不存在，和绿色线相交必定和橙色线相交。
如下图。

这根紫色的线，可以动手画画看，看能不能画出和绿色相交但是不和橙色相交的线。（前提是位置在下面，上限不能超过target）

那么现在，我们可以从最高的线开始，看下面也就是除我之外最高的和我相交吗，如果没有，那下面就不可能再有线条和我相交了，因为都会被第二高的线条挡住。
到这里，可以得到初步结论：我们必须从位置最高的开始，也就是说，要经历排序。
我们用一个变量来记录答案。初始化为1，因为至少有一个车队。
然后看第二高的，是否能和第一高的相交

1. 如果相交。那么第二高的直接与第一高的合并
2. 如果不相交，那么答案+1
   代码：

class Solution {    class CarTime{ int position; float spendTime; public CarTime(int position, float spendTime){     this.position = position;     this.spendTime = spendTime; }    }    public int carFleet(int target, int[] position, int[] speed) { int n = position.length; CarTime[] datas = new CarTime[n];  for(int i = 0; i < n; i++){     datas[i] = new CarTime(position[i], (target-position[i])*1.0F / speed[i]); } //降序 Arrays.sort(datas, new Comparator<CarTime>() {     @Override     public int compare(CarTime o1, CarTime o2) {  return o2.position - o1.position;     } }); int res = 1; //后面的起始点更低 for(int i =0  ; i+1 < n ;i++){     if(datas[i].spendTime >= datas[i+1].spendTime){  //如果相交。那么第二高的直接与第一高的合并  datas[i+1] =datas[i];     }else{  //如果不相交，那么答案+1  res++;     } } return res;    }}