<p>There are <code>n</code> cars traveling at different speeds in the same direction along a one-lane road. You are given an array <code>cars</code> of length <code>n</code>, where <code>cars[i] = [position<sub>i</sub>, speed<sub>i</sub>]</code> represents:</p>

<ul>
	<li><code>position<sub>i</sub></code> is the distance between the <code>i<sup>th</sup></code> car and the beginning of the road in meters. It is guaranteed that <code>position<sub>i</sub> &lt; position<sub>i+1</sub></code>.</li>
	<li><code>speed<sub>i</sub></code> is the initial speed of the <code>i<sup>th</sup></code> car in meters per second.</li>
</ul>

<p>For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the <strong>slowest</strong> car in the fleet.</p>

<p>Return an array <code>answer</code>, where <code>answer[i]</code> is the time, in seconds, at which the <code>i<sup>th</sup></code> car collides with the next car, or <code>-1</code> if the car does not collide with the next car. Answers within <code>10<sup>-5</sup></code> of the actual answers are accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cars = [[1,2],[2,1],[4,3],[7,2]]
<strong>Output:</strong> [1.00000,-1.00000,3.00000,-1.00000]
<strong>Explanation:</strong> After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cars = [[3,4],[5,4],[6,3],[9,1]]
<strong>Output:</strong> [2.00000,1.00000,1.50000,-1.00000]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= cars.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= position<sub>i</sub>, speed<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
	<li><code>position<sub>i</sub> &lt; position<sub>i+1</sub></code></li>
</ul>

class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        n = len(cars)
        if n==1:
            return [-1.0]
        
        ans = [-1 for i in range(n)]
        st = []
        st.append(n-1)
        for i in reversed(range(n-1)):
            curpos = cars[i][0]
            curspeed = cars[i][1]
            #print(f"a i:{i} ans:{ans}")
            while len(st):
                nxt = st[-1]
                nxtpos=cars[nxt][0]
                nxtspeed = cars[nxt][1]
                if nxtspeed >= curspeed:
                    st.pop()
                else:
                    break
            
            #print(f"b: i {i} st:{st}")

            if len(st) ==0:
                ans[i] = -1
                st.append(i)
                continue
            
            ni = len(st)-1
            nxt = st[ni]
            nxtpos=cars[nxt][0]
            nxtspeed = cars[nxt][1]
            distance = nxtpos - curpos

            #t = distance/(curspeed-nxtspeed)

            while ans[nxt]!=-1 and distance/(curspeed-nxtspeed) > ans[nxt] and len(st):
                st.pop()
                ni=len(st)-1
                nxt = st[ni]
                nxtpos=cars[nxt][0]
                nxtspeed = cars[nxt][1]
                distance = nxtpos - curpos
            #print(f"c: i {i} st:{st}")
            
            stlen=len(st)

            if len(st) ==0:
                ans[i]=-1
                st.append(i)
                continue
            else:
                t= distance/(curspeed -nxtspeed)
                ans[i] = t
            #if ans[i] != -1:
            st.append(i)
            
        return ans
            


            



            


        
1479