題目列表

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;}
};