首页 > 分享 > leetcode 6044. 花期内花的数目 —（每日一难day1）

leetcode 6044. 花期内花的数目 —（每日一难day1）

花匠小妙招
2024-08-19 05:36

6044. 花期内花的数目显示英文描述

给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的花期从 starti 到 endi （都包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 persons ，persons[i] 是第 i 个人来看花的时间。

请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的数目。

示例 1：

在这里插入图片描述
输入：flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
输出：[1,2,2,2]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。对每个人，我们返回他们到达时在花期内花的数目。

示例 2：

在这里插入图片描述

输入：flowers = [[1,10],[3,3]], persons = [3,3,2]
输出：[2,2,1]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。对每个人，我们返回他们到达时在花期内花的数目。
在这里插入图片描述

提示：

1 <= flowers.length <= 5 * 1e4
flowers[i].length == 2
1 <= starti <=endi <= 1e9
1 <= persons.length <= 5 * 1e4
1 <= persons[i] <= 1e9

解析：
1，如果可以维护一个数组t，t[i]表示第i时刻可以观察到花的数目，那么只需要按照时刻返回当前花的数目。
2，t 数组又怎么得到呢？t数组是一个前缀和，首先，遍历flowers,让t[starti]++记录在starti时刻开放的数目 , t[endi+1]–表示在endi凋谢花的数目，因为在endi花还在，所以endi+1才会失去。然后，得到t数组的前缀和数组。
3，很明显，时刻较大，因此需要离散化处理。通过map记录每一个时间点，然后为每个时间点分配一个新的下标。

code：

class Solution { public: map<int,int> ma , idx; int t[200000]; vector<int> fullBloomFlowers(vector<vector<int>>& f, vector<int>& p) { memset(t,0,sizeof(t)); int n = f.size(); int m = p.size(); // 将需要用到的关键点加入 for(auto a:f){ ma[a[0]]=1; ma[a[1]]=1; } for(auto a:p) ma[a]=1; // 为每个关键点分配新的下标，并且使用map维持他们的对应关系 int cnt=0; for(auto a:ma) idx[a.first]=++cnt; // a[0]表示开花时间，idx[a[0]]表示对应的新坐标， for(auto a:f){ t[idx[a[0]]]++; t[idx[a[1]]+1]--; } // 前缀和，可以发现下标分配从1开始，因此这里不用考虑0 for(int i=1;i<200000;i++){ t[i]+=t[i-1]; } vector<int> res; for(auto a : p){ res.push_back(t[idx[a]]); } return res; } };

1234567891011121314151617181920212223242526272829303132333435

参考代码地址