Leetcode 853 车队

题目挺简单的,但是这题是我筛选单调栈的时候筛选到的,结果想了半天也不知道怎么用单调栈解…….因为感觉就是按位置从近到远排序后遍历,如果发现时间更长的,就代表它可以形成一个新的车队。但是看了题解发现有用单调栈的,看了半天才看懂。其实抽象出来的模型应该是一样的吧(我也不知道是什么模型),但他们的排序用的是从远到近的排序。如果使用从远到近排序的话,就不能简单的贪心来解决了。
举个例子吧,比如说(时间) 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;
    }

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

大纲

Share the Post:
滚动至顶部