---
# System prepended metadata

title: 0853. Car Fleet
tags: [Leetcode, Monotonic Stack, Medium]

---

# 0853. Car Fleet
###### tags: `Leetcode` `Medium` `Monotonic Stack`
Link: https://leetcode.com/problems/car-fleet/description/
## 思路
不能完全算是一道monotonic stack题目
如果两辆车A和B A的起始位置在B的后面 但是A比B先到或者一起到终点 那么他们就会相遇 并且形成fleet
按照position排好序 然后根据position从大到小 加进stack 如果现在元素到达时间不是目前为止最长的 说明前面肯定有其他车比他晚到 或者同时到 那么他们就可以形成一个车队
## Code
```python=
class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        time = [(target-p)/s for p, s in sorted(zip(position, speed), key = lambda ab:-ab[0])]
        ans = curLongest = 0
        for t in time:
            if t>curLongest:
                curLongest = t
                ans += 1
        return ans
```
```java=
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        Map<Integer, Double> map = new TreeMap<>(Collections.reverseOrder());
        for(int i=0; i<position.length; i++){
            map.put(position[i], (double)(target-position[i])/speed[i]);
        }
        double currLongest = 0;
        int res = 0;
        for(Map.Entry<Integer, Double> e:map.entrySet()){
            System.out.println(e.getKey());
            if(e.getValue()>currLongest){
                currLongest = e.getValue();
                res++;
            }
        }
        return res;
    }
}
```