google phone interview

假设有一条高速公路，路面上有n辆车，每辆车有不同的整数速度，但是都在1-n范围内。现在给你一个数组，代表每辆车的速度。车辆出发顺序即数组顺序，问最后可以形成几个集群，每个集群的size是多少？ 可以理解为，虽然车辆速度不同，但是即使后面的车比前面的车速度快，因为不能超车，最后肯定只能以前车的速度行驶，这就形成了一个集群。比如[2,4,1,3]，最后[2,4]是一个集群，[1,3]是一个集群。

Follow up是现在假设想再加入一辆车，这个车的速度比其他车都大，但是不确定这个车的出发顺序，让输出最后所有可能的每个集群的大小（List of List）。要求是可以调整并调用之前的函数，但是只能调用一次。思路还是比较直接的，但是当时太紧张了，不知道怎么去实现，耽误了好久，写到最后发现有bug...但是小哥好像没发现= = 最后问了几个问题结束了。