LeetCode---386周赛

题目列表

3046. 分割数组

3047. 求交集区域内的最大正方形面积

3048. 标记所有下标的最早秒数 I

3049. 标记所有下标的最早秒数 II

一、分割数组

这题简单的思维题，要想将数组分为两个数组，且分出的两个数组中数字不会重复，很显然一个数字出现次数最多两次，代码如下

class Solution {
public:bool isPossibleToSplit(vector<int>& nums) {unordered_map<int,int>mp;for(auto x:nums)if(++mp[x]>2)return false;return true;}
};

二、求交集区域内的最大正方形面积

直接暴力枚举出所有两个矩阵的交集的正方形面积，求解出最大值，代码如下

class Solution {
public:long long largestSquareArea(vector<vector<int>>& bLeft, vector<vector<int>>& tRight) {int n=bLeft.size(),w=0;for(int i=1;i<n;i++){for(int j=i-1;j>=0;j--){//挑选四个直线，围成交集区域int x_l=max(bLeft[i][0],bLeft[j][0]);int x_r=min(tRight[i][0],tRight[j][0]);int y_top=min(tRight[i][1],tRight[j][1]);int y_bottom=max(bLeft[i][1],bLeft[j][1]);if(x_l<x_r&&y_top>y_bottom){//确保会有交集w=max(w,min(x_r-x_l,y_top-y_bottom));}}    }return 1LL*w*w;}
};

三、标记所有下标的最早秒数I

题目问最早秒数，我们正常来说都会想到贪心 / 从小到大枚举验证，其中贪心，大家可以去试着想想，因为需要从左往右遍历时间，而我们不知道后面changeIndices[]的情况，所以就不能去决定这一步去做什么操作会比较好，也就很难去贪心。

那么我们来看看枚举验证行不行？一旦数据不好，估计得验证O(n)次，大概率会超时，所以我们要降低时间复杂度，怎么做？--- 二分

1、是否满足二分条件，即单调性？

根据题目所给的条件，我们知道时间越多，我们越有可能将nums[i]减为零，越有可能标记所有下标，即秒数越多越能满足条件，符合单调性，可以二分

2、如何验证是否能在k秒内标记所有下标，即bool check(int k)函数如何写？(如果下面的内容不理解，可以先看看下面加粗的内容)

首先，由于changeIndices[]是不可预知的，即标记操作是不可控的，所以我们优先考虑什么时候标记下标的问题，根据贪心，我们肯定是越晚标记下标越好，这样会有更多的时间将nums[i]减为零，所以我们要知道每个下标的最晚标记时间

然后在来考虑是否能在下标 i 的最晚标记时间之前，将nums[i]减为零，这个就很简单了，我们只要维护一个cnt来记录到目前为止有多少时间，然后在到达某个最晚标记时间时，如果cnt>=nums[i]，cnt = cnt - nums[i]，否则直接返回false，如果所有下标都能被标记就返回true (很显然check函数的时间复杂度为O(n)，所以暴力枚举会超时，需要二分)

如果大家不是很理解，可以将这题转换成考试来看，即一共有n门课程，nums[i]表示第 i 门课程的复习天数，changeIndices[i]表示第 i 天进行考试的课程，问复习完并考完所有课程的最少天数是多少？相信经历了这么多年考试的你们，会更容易理解复习和考试的关系(doge)

代码如下

/*
将问题转换成一共有n门课程，第i门课程的复习时间为nums[i]天
changeIndices[i]课程的考试时间为第i天
复习并考完所有课程的最小时间由于考试时间是固定的，我们需要优先考虑考试时间
=> 考试时间越靠后，就会有更加充分的时间用来复习
=> 具有单调性
=> 可以二分check函数如何去判断是否能复习考完所有的考试？
1、贪心，我们把每门课程的考试时间尽可能往后拖延  last[]记录每门课程的最迟考试时间
2、如果考试数目<=课程数，return false; // 可以优化的点否则我们从前往后遍历天数，优先复习考试时间近的科目，看能否在考试之前完成复习
*/class Solution {
public:int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {int n=nums.size(),m=changeIndices.size();auto check=[&](int k)->bool{vector<int>last(n,-1); // 记录下标i的最晚标记时间，即最晚考试时间for(int i=0;i<k;i++)last[changeIndices[i]-1]=i;for(auto x:last)if(x<0) // 表示有的下标没有被标记的时间，即有的课程没有考试return false;int cnt = 0;for(int i=0;i<k;i++){int idx = changeIndices[i] - 1;if(last[idx]==i){//表示下标idx到了最后的被标记的时间，即课程到了考试的最后截止时间cnt-=nums[idx];if(cnt<0) return false;//没有足够的时间将nums[idx]置为0，即没有足够的时间复习课程}else{cnt++;}}return true;};int l=1,r=m;while(l<=r){int mid = l+(r-l)/2;if(check(mid)) r=mid-1;else l=mid+1;}return l>m?-1:l;}
};

四、标记所有下标的最早秒数II

有情提醒一下： 该题和第三题的题目并不一样。

在这题中，操作变得更加复杂了，但其实我们还是可以借鉴第三题的思路：

首先，这题依旧能够二分，因为时间越多，越有可能标记所有下标，但是check函数的思路不一样了，我们要优先考虑清零操作，因为它是不可控的(为了方便描述，这里将题目中的几个操作分别称为减一、清零、标记)。

【如果下面的内容看不太明白，依旧可以带入上一题说的考试模型，帮助你理解---减一操作：花费一天复习一门课，清空操作：花费一天速通一门课，标记：选择一天用来考试】

1）这里就要讨论一下：清零操作和减一操作什么时候用比较合适？

1、如果nums[i]用过减一操作，还需要用清零操作吗？没必要，因为如果能清零，就没必要在花多余的时间进行减一，可以将多出的时间给其他的nums[j]

2、如果nums[i]用过清零操作，也就不需要在进行减一操作了

结论：对于nums[i]要么执行清零操作，要么就执行减一操作，不能混用

2）根据贪心：我们肯定是能清零就尽量的去执行清零，让被清零的nums[i]有更多的时间被减为0

1、清零操作是越早越好还是越晚越好？肯定是越早越好，因为我们还需要有多余的时间去标记，所以我们需要从后往前遍历，去看是否有多余的时间去标记下标，所以我们要记录每个下标的最早清零时间

2、什么时候不需要用清零操作？

• nums[i]==0时，不需要
• nums[i]==1时，也不需要，因为减一操作也能做到清零，且可以在任意时间执行

除了上面的两种情况，还有一种特殊的情况，即用完清零操作之后就没时间进行标记了，这里我们不是只能进行对 i 下标进行nums[i]次减一操作，而是可以看之前进行清空操作的下标中nums[j]的最小值 是否 比nums[i]小，如果小，那么显然我们可以对 j 下标进行nums[j]次减一操作，同时nums[i]就会有时间进行清零和标记，这样的方案显然会更优----反悔贪心

我们从后往前遍历，同时维护用来标记/减一的时间cnt 和 需要减一和标记的总时间sum（都不包含进行清零操作的下标的标记时间）具体如何维护看下面的代码。

class Solution {
public:int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {int n=nums.size(),m=changeIndices.size();long long total = n;for(auto x:nums) total += x;            vector<int>first_d(n,-1);for(int i=m-1;i>=0;i--)first_d[changeIndices[i]-1]=i;auto check=[&](int k)->bool{priority_queue<int,vector<int>,greater<int>> q;int cnt = 0;// 减一复习并考试的课程的所有时间long long slow = total;//记录减一操作的nums[i]及其标记需要的时间，一开始默认全用减一操作for(int i=k-1;i>=0;i--){int idx=changeIndices[i]-1;if(nums[idx]<=1||i!=first_d[idx]){cnt++;continue;}if(cnt==0){if(q.empty()||nums[idx]<=q.top()){//只能进行减一操作cnt++;continue;}slow += q.top()+1;q.pop();cnt += 2;}slow -= nums[idx]+1;cnt--;q.push(nums[idx]);}return cnt>=slow;};int l=1,r=m;while(l<=r){int mid=l+(r-l)/2;if(check(mid)) r=mid-1;else l=mid+1;}return l>m?-1:l;}
};