题目挺简单的,但是这题是我筛选单调栈的时候筛选到的,结果想了半天也不知道怎么用单调栈解…….因为感觉就是按位置从近到远排序后遍历,如果发现时间更长的,就代表它可以形成一个新的车队。但是看了题解发现有用单调栈的,看了半天才看懂。其实抽象出来的模型应该是一样的吧(我也不知道是什么模型),但他们的排序用的是从远到近的排序。如果使用从远到近排序的话,就不能简单的贪心来解决了。
举个例子吧,比如说(时间) 9 6 3 2 8 这样的序列,如果从后向前遍历很容易就得到8 9是符合的。但是如果是从前向后遍历,先取了9,而后发现6更小,3,2,后来又发现8更大,因为8在前面,所以会挡住后面所有比8小(快)的,所以6 3 2都被挡住了就合并成一个车队,无效了,所以这时候需要把6 3 2变成8。而这个操作正好是单调栈所合适的。
所以本质上,使用贪心就够了,还是要使用单调栈才可以,是通过遍历顺序决定的。从后往前找很简单,但是从前往后找很难(虽然搞不懂深层本质,但是栈本身就是保留调用顺序的一种东西,比如说函数栈)
至于再深层的原理,目前的我还是搞不清楚,希望以后可以再补一补这个部分~
最后贴上自己的贪心渣解:
bool static myCompare(pair<int, double> a, pair<int, double> b) { return a.first > b.first; } int carFleet(int target, vector<int>& position, vector<int>& speed) { vector<pair<int, double>> v; for(int i=0;i<position.size();i++){ v.push_back(pair<int, double>(position[i], (double)(target - position[] ) / speed[i])); } std::sort(v.begin(), v.end(), myCompare); double cur = 0; int cnt = 0; for(int i=0;i<v.size();i++){ if (v[i].second <= cur){ }else{ cnt ++; cur = v[i].second; } } return cnt; }