文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

在一條單車道上有 n 輛車，它們朝著同樣的方向行駛。
給你一個(gè)長(zhǎng)度為 n 的數(shù)組 cars ，其中 cars[i] = [positioni, speedi] ，它表示：

• positioni 是第 i 輛車和道路起點(diǎn)之間的距離（單位：米）。
  題目保證 positioni < positioni+1 。
• speedi 是第 i 輛車的初始速度（單位：米/秒）。

簡(jiǎn)單起見，所有車子可以視為在數(shù)軸上移動(dòng)的點(diǎn)。
當(dāng)兩輛車占據(jù)同一個(gè)位置時(shí)，我們稱它們相遇了。
一旦兩輛車相遇，它們會(huì)合并成一個(gè)車隊(duì)，這個(gè)車隊(duì)里的車有著同樣的位置和相同的速度，速度為這個(gè)車隊(duì)里 最慢 一輛車的速度。

請(qǐng)你返回一個(gè)數(shù)組 answer ，其中 answer[i] 是第 i 輛車與下一輛車相遇的時(shí)間（單位：秒），如果這輛車不會(huì)與下一輛車相遇，則 answer[i] 為 -1 。
答案精度誤差需在 10-5 以內(nèi)。

示例 1： 輸入：cars = [[1,2],[2,1],[4,3],[7,2]] 輸出：[1.00000,-1.00000,3.00000,-1.00000] 解釋：經(jīng)過恰好 1 秒以后，第一輛車會(huì)與第二輛車相遇，并形成一個(gè) 1 m/s 的車隊(duì)。 經(jīng)過恰好 3 秒以后，第三輛車會(huì)與第四輛車相遇，并形成一個(gè) 2 m/s 的車隊(duì)。示例 2： 輸入：cars = [[3,4],[5,4],[6,3],[9,1]] 輸出：[2.00000,1.00000,1.50000,-1.00000]提示： 1 <= cars.length <= 10^5 1 <= positioni, speedi <= 10^6 positioni < positioni+1

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/car-fleet-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

類似題目：LeetCode 853. 車隊(duì)（排序）

class Solution { public:vector<double> getCollisionTimes(vector<vector<int>>& cars) {int n = cars.size();vector<double> ans(n, -1.0);stack<int> s;for(int i = n-1; i >= 0; i--) {while(!s.empty() && (cars[s.top()][1] >= cars[i][1] || (ans[s.top()] > 0 && delta(cars, i, s.top()) > ans[s.top()]))){ // 我的速度沒有前車大，追不上前面的，檢查再前面的人，前面可能有更慢的//前車 top 能撞上別人 且 撞上別人的時(shí)間 小于 我撞上top的時(shí)間，那我應(yīng)該去跟更前面的人計(jì)算// 因?yàn)榍败?top 已經(jīng)先于我 撞上更前面的s.pop();}if(!s.empty())ans[i] = delta(cars, i, s.top());s.push(i);}return ans;}double delta(vector<vector<int>>& cars, int i, int j)//j 位置遠(yuǎn)，速度慢{return (cars[j][0] - cars[i][0])/double(cars[i][1] - cars[j][1]);} };

572 ms 122.8 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1776. 车队 II（单调栈）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。