今天刷到一道挺有意思的题,叫“无敌车队”,听这名字就觉得挺唬人的,必须得研究研究。
一开始没啥思路,就想着先在纸上比划比划。我这人有个习惯,遇到搞不懂的问题,就喜欢在纸上写写画画,有时候画着画着就有灵感。
我把题目给的要求都捋一遍。大概意思就是有一堆车,它们在一条道上跑,每辆车有自己的位置和速度。然后问你,能形成几个车队。这里头有个规矩,就是后面的车要是速度比前面的车快,那它早晚能追上前面的车,追上之后就并成一个车队,速度就得跟着前面的车走。
我先随便写几个车的初始位置和速度:
- 第一辆车:位置 0,速度 5
- 第二辆车:位置 3,速度 2
- 第三辆车:位置 5,速度 8
- 第四辆车:位置 8,速度 3
然后,我开始推演。第一辆车和第二辆车,因为第一辆车速度快,所以它俩不会合并。第三辆车位置比第二辆车靠后,但速度快多,所以肯定能追上第二辆车,合并成一个车队。这时候,这个车队的速度就变成 2 。然后第四辆车,虽然位置靠后,但是速度比前面这个车队快,所以也会合并进去。
这么一分析,我发现这里头有个关键点:后面车的速度只要比前面车队里最慢的那辆车快,就一定会合并进去。这么一来,问题就简单。
我琢磨着,可以用一个列表来记录当前每个车队的速度。然后从一辆车开始往前推。为啥要从后往前?因为后面的车队形成之后,就不会再变,方便计算。
具体咋操作?我就拿上面那个例子来说:
- 车队列表是空的。
- 先看第四辆车,速度是 3。因为前面没有车队,所以它自己就是一个车队,把 3 加到车队列表里。现在列表是 [3]。
- 再看第三辆车,速度是 8。比前面的车队速度快,所以合并,不加到列表里。
- 看第二辆车,速度是 2。比前面的车队速度慢,所以它自己会形成一个新的车队,把 2 加进去。现在列表是 [3, 2]。
- 看第一辆车,速度是 5。比它后面那个车队(速度是2)要快,所以合并。
这么跑一遍下来,车队列表里剩几个数字,就说明有几个车队。上面这个例子,列表是 [3, 2],所以就是两个车队。
搞明白这个,剩下的就是写代码的事。代码写完,跑几个测试用例,都没问题,这题就算搞定!
今儿这实践,感觉还挺有收获的,把一个听起来挺吓人的问题,一步步拆解,给解决。以后再遇到这种问题,也更有信心!