LeetCode 2136. 全部开花的最早一天

题目描述

解题思路

代码

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

bool cmp(PII a, PII b)
{
    //升序排序
    return a.first > b.first;
}

class Solution {
public:
    int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
        
        int n = plantTime.size();

        vector<PII> rec;
        for(int i = 0; i < n; i++)
        {
            rec.push_back({growTime[i], plantTime[i]});
        }
        sort(rec.begin(),rec.end(),cmp);

        int res = 0, ed = 0;//ed是种植结束的时间，res是最终时间
        for(auto item : rec)
        {
            int gt = item.first, pt = item.second;
            ed += pt;
            res = max(res, ed + gt);
        }
        return res;
    }
};

关于排序，可以使用一个vector存储下标，然后对下标进行排序，使用lambda自定义排序函数（在cmp里面实现也行，但是两个数组不是全局变量有点麻烦） 十分巧妙！

#include<bits/stdc++.h>

using namespace std;

class Solution {
public:
    int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {

        int n = plantTime.size();

        vector<int> order(n);
        for(int i = 0; i < n; i++)
            order[i] = i;
        
        //使用lambda进行排序
        //捕获外部作用域中所有变量，并作为引用在函数体中使用（按引用捕获）
        sort(order.begin(), order.end(), [&](int i, int j){
            return growTime[i] > growTime[j];
        });

        int ans = 0, ed = 0;
        for(int i : order)
        {
            ed += plantTime[i];
            ans = max(ans, ed + growTime[i]);
        }
        return ans;
    }
};