難度：★★★☆☆
類型：數(shù)組
方法：棧
力扣鏈接請(qǐng)移步本題傳送門
更多力扣中等題的解決方案請(qǐng)移步力扣中等題目錄
題目
N 輛車沿著一條車道駛向位于 target 英里之外的共同目的地。
每輛車 i 以恒定的速度 speed[i] （英里/小時(shí)），從初始位置 position[i] （英里） 沿車道駛向目的地忘晤。
一輛車永遠(yuǎn)不會(huì)超過前面的另一輛車累盗，但它可以追上去勾拉，并與前車以相同的速度緊接著行駛炒考。
此時(shí)宰翅，我們會(huì)忽略這兩輛車之間的距離噩死，也就是說颤难，它們被假定處于相同的位置。
車隊(duì) 是一些由行駛在相同位置已维、具有相同速度的車組成的非空集合行嗤。注意，一輛車也可以是一個(gè)車隊(duì)垛耳。
即便一輛車在目的地才趕上了一個(gè)車隊(duì)栅屏，它們?nèi)匀粫?huì)被視作是同一個(gè)車隊(duì)。
會(huì)有多少車隊(duì)到達(dá)目的地?
示例：
輸入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
輸出：3
解釋：
從 10 和 8 開始的車會(huì)組成一個(gè)車隊(duì)堂鲜，它們?cè)?12 處相遇栈雳。
從 0 處開始的車無(wú)法追上其它車，所以它自己就是一個(gè)車隊(duì)缔莲。
從 5 和 3 開始的車會(huì)組成一個(gè)車隊(duì)哥纫，它們?cè)?6 處相遇。
請(qǐng)注意酌予，在到達(dá)目的地之前沒有其它車會(huì)遇到這些車隊(duì)磺箕，所以答案是 3。
提示：
0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
所有車的初始位置各不相同抛虫。
解答
假設(shè)每輛車從左到右行駛松靡，我們把每個(gè)車及其對(duì)應(yīng)的速度從左到右排列好，然后計(jì)算出每輛車到達(dá)終點(diǎn)所需要的時(shí)間建椰。我們把每輛車到達(dá)終點(diǎn)的時(shí)間按照起始位置的順序放在一個(gè)棧中雕欺，棧頂元素是最接近終點(diǎn)的。
我們從最接近終點(diǎn)的車開始研究棉姐，如果這個(gè)車到達(dá)終點(diǎn)的時(shí)間比前一個(gè)車要長(zhǎng)屠列，說明兩個(gè)車一定相遇了，如果相遇伞矩，則兩個(gè)車到達(dá)終點(diǎn)的時(shí)間由時(shí)間較長(zhǎng)的后面的車決定笛洛，否則，說明前面的車已經(jīng)自成一隊(duì)乃坤，結(jié)果加1苛让。
這里需要注意兩車相遇時(shí)的處理沟蔑，如果相遇的話我們需要及時(shí)調(diào)整棧頂元素也就是后一輛車的到達(dá)時(shí)間為前一輛車的時(shí)間。
class Solution:
def carFleet(self, target, position, speed):
times = [float(target - p) / s for p, s in sorted(zip(position, speed))]
ans = 0
while times:
lead = times.pop()
if not times or lead < times[-1]:
ans += 1
else:
times[-1] = lead
return ans
如有疑問或建議狱杰，歡迎評(píng)論區(qū)留言~
有關(guān)更多力扣中等題的python解決方案瘦材，請(qǐng)移步力扣中等題解析
