本文涉及的基礎(chǔ)知識(shí)點(diǎn)

二分查找

題目

給你一個(gè)二維整數(shù)數(shù)組 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 個(gè)信封的寬度和高度。
當(dāng)另一個(gè)信封的寬度和高度都比這個(gè)信封大的時(shí)候，這個(gè)信封就可以放進(jìn)另一個(gè)信封里，如同俄羅斯套娃一樣。
請(qǐng)計(jì)算 最多能有多少個(gè) 信封能組成一組“俄羅斯套娃”信封（即可以把一個(gè)信封放到另一個(gè)信封里面）。
注意：不允許旋轉(zhuǎn)信封。
示例 1：
輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出：3
解釋：最多信封的個(gè)數(shù)為 3, 組合為: [2,3] => [5,4] => [6,7]。
示例 2：
輸入：envelopes = [[1,1],[1,1],[1,1]]
輸出：1
參數(shù)提示：
1 <= envelopes.length <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105

超時(shí)解法

有兩個(gè)地方可能超時(shí)：
一，std::map<int, int> dp = mPreYToNum;
二，for (; (ij != dp.end()) && (ij->second > len); ++ij);
一處的時(shí)間復(fù)雜度是:O(n)，最多有n個(gè)元素，所以總時(shí)間復(fù)雜度是O(n*n)，會(huì)引起超時(shí)。
二處，總時(shí)間復(fù)雜度是O(n)，最多刪除n次，每個(gè)元素最多只會(huì)被刪除一次。

代碼

class Solution {
public:
int maxEnvelopes(vector<vector>& envelopes) {
std::map<int, vector> mXToYS;
for (const auto& v : envelopes)
{
mXToYS[v[0]].emplace_back(v[1]);
}
std::map<int, int> mPreYToNum;//y值對(duì)應(yīng)最大數(shù)量，y值越大，對(duì)應(yīng)的數(shù)量越大，否則被淘汰了
int iMax = 0;
for (const auto& it : mXToYS)
{
std::map<int, int> dp = mPreYToNum;
for (const auto& y : it.second)
{
int len = 0;
{//計(jì)算長(zhǎng)度
const auto it = mPreYToNum.lower_bound(y);
len = 1 + ((mPreYToNum.begin() == it) ? 0 : std::prev(it)->second);
iMax = max(iMax, len);
}
{
const auto it = dp.lower_bound(y);
auto ij = it;
for (; (ij != dp.end()) && (ij->second > len); ++ij);
dp.erase(it, ij);
if (!dp.count(y))
{
dp[y] = len;
}
}
}
mPreYToNum.swap(dp);
}

	return iMax;
}

};

測(cè)試用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i] ,v2[i]);
}
}

int main()
{
Solution slu;
vector<vector> envelopes;
int res = 0;
envelopes = { {5,4},{6,4},{6,7},{2,3} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 3);
envelopes = { {1,1},{1,1},{1,1} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 1);
envelopes = { {1,1},{2,2},{2,3} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 2);
envelopes = { {1,2},{2,3},{3,4},{3,5},{4,5},{5,5},{5,6},{6,7},{7,8} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 7);

//CConsole::Out(res);

}

正確解法

變量含義

mXToYS	key為envelopes的x，值為envelopes的y
mYToNum	[x取[0,x)， y對(duì)應(yīng)最大套娃數(shù)量
vector<pair<int, int>> vYNum	當(dāng)前x，各y對(duì)應(yīng)數(shù)量

注意：

x相同，無(wú)法套娃，所以必須等當(dāng)前x處理完畢，才能更新mYToNum。
y值越大，對(duì)應(yīng)的數(shù)量越大，否則被淘汰了。所以mYToNum的鍵和值都是升序。
y小于當(dāng)前y的，不會(huì)淘汰當(dāng)前y，因?yàn)楫?dāng)前長(zhǎng)度就是小于y的最大長(zhǎng)度+1。
所以只會(huì)被相等的y淘汰。
當(dāng)前y 可能淘汰比當(dāng)前y大的。

代碼

class Solution {
public:
int maxEnvelopes(vector<vector>& envelopes) {
std::map<int, vector> mXToYS;
for (const auto& v : envelopes)
{
mXToYS[v[0]].emplace_back(v[1]);
}
std::map<int, int> mYToNum;//y值對(duì)應(yīng)最大數(shù)量
int iMax = 0;
for (const auto& it : mXToYS)
{
vector<pair<int, int>> vYNum;
for (const auto& y : it.second)
{
const auto it = mYToNum.lower_bound(y);
const int num = 1 + ((mYToNum.begin() == it) ? 0 : std::prev(it)->second);
iMax = max(iMax, num);
vYNum.emplace_back(y, num);
}
for(const auto[y,num]: vYNum)
{
const auto it = mYToNum.lower_bound(y);
auto ij = it;
for (; (ij != mYToNum.end()) && (ij->second <= num); ++ij);
mYToNum.erase(it, ij);
if (!mYToNum.count(y))
{
mYToNum[y] = num;
}
}
}
return iMax;
}
};

2023年1月舊代碼

class Solution {
public:
int maxEnvelopes(vector<vector>& envelopes) {
std::map<int, vector> mWidthToHeights;
for (const auto& v : envelopes)
{
mWidthToHeights[v[0]].push_back(v[1]);
}
int iMax = 1;
std::map<int, int> mHeightNum;
for ( auto& it : mWidthToHeights)
{
sort(it.second.begin(), it.second.end(),std::greater());
for (auto& height : it.second)
{
auto it = mHeightNum.lower_bound(height);
int iNum =1;
if (mHeightNum.begin() != it)
{//沒(méi)有套
auto ij = it;
–ij;
iNum = ij->second + 1;
}
iNum = max(iNum,mHeightNum[height]);
auto ij = it;
while ( (ij != mHeightNum.end())&& ( ij->second < iNum))
{
ij++;
}
mHeightNum.erase(it, ij);
mHeightNum[height] = max(mHeightNum[height], iNum);
iMax = max(iMax, mHeightNum[height]);
}
}
return iMax;
}
};

擴(kuò)展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡(jiǎn)單的課程，請(qǐng)移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請(qǐng)學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)下載

想高屋建瓴的學(xué)習(xí)算法，請(qǐng)下載《聞缺陷則喜算法冊(cè)》doc版
https://download.csdn.net/download/he_zhidan/88348653

充滿正能量得對(duì)大家說(shuō)
聞缺陷則喜是一個(gè)美好的愿望，早發(fā)現(xiàn)問(wèn)題，早修改問(wèn)題，給老板節(jié)約錢。
墨家名稱的來(lái)源：有所得以墨記之。
算法終將統(tǒng)治宇宙，而我們統(tǒng)治算法。《喜缺全書》

測(cè)試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開

發(fā)環(huán)境： VS2022 C++17