力扣題解《禁止套娃＝烨簟（圖解過程）》
方法一：比較暴力的動態(tài)規(guī)劃
思路
-
狀態(tài)定義:
-
表示僅使用信封
(這里是區(qū)間的意思，表示前
個信封)，且以第
個信封為頂端信封時的最大高度盾鳞。
-
-
狀態(tài)轉(zhuǎn)移:
- 首先對整個數(shù)組根據(jù)寬度排序，寬的信封放在前面瞻离。
- 設(shè)
,考慮每輪計算新的
區(qū)間，做以下判斷：
-
當(dāng)
且
時：認為信封
嚴格大于信封
:
maxh = max(maxh, dp[j]) -
當(dāng)信封
- 全部遍歷完成后，更新
dp[i] = maxh + 1肉迫。理解為在最大可放置的高度上验辞，再放上當(dāng)前信封。 -
轉(zhuǎn)移方程：
dp[i] = max(dp[j]) + 1 (j ∈ [0, i) 且信封j比信封i嚴格大)
-
初始狀態(tài):
-
-
-
返回值:
- 返回
列表最大值，即可得最大套娃層數(shù)格侯。
- 返回
復(fù)雜度分析
時間復(fù)雜度
：排序需要
鼻听，遍歷
财著，計算每一個
空間復(fù)雜度
快樂小視頻
具體代碼：
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
// 先按照寬做排序，越大的放在越前面
sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b){
return a[0] > b[0];
});
// 預(yù)開空間(不妨多開幾個防溢出)
vector<int> dp(n + 5);
int ans = 0;
// 依次嘗試放置每個信封
for(int i = 0; i < n; i++){
// 遍歷他之前的每個信封撑碴，看能放下他且最多層的個數(shù)
int maxh = 0;
for(int j = 0; j < i; j++){
// 判斷是否可以放下當(dāng)前的信封
if(envelopes[j][0] > envelopes[i][0]
&& envelopes[j][1] > envelopes[i][1]){
// 如果可以放下當(dāng)前信封撑教，看看是不是最大高度
if(maxh < dp[j]){
maxh = dp[j];
}
}
}
// 遍歷一圈，找到最高醉拓，且能放下當(dāng)前信封的maxh
dp[i] = maxh + 1;
// 判斷當(dāng)前信封高度是不是最高高度
ans = max(ans, dp[i]);
}
return ans;
}
};
用C++提交花費了1264 ms伟姐，確實挺慢的，看其他題解里寫不同語言可能會超時亿卤。
但是確實這個思路最好想愤兵，也可以很方便的套用到面試題 08.13. 堆箱子這道題上。
方法二：第二維參與排序
思路
目標(biāo)是將二維問題排吴，轉(zhuǎn)換為我們所熟悉的一維的最長上升子序列問題秆乳。因此需要降維，想辦法在計算時钻哩，僅考慮 的順序即可屹堰，忽略
影響。
-
狀態(tài)定義:
-
-
-
狀態(tài)轉(zhuǎn)移:
- 首先對整個數(shù)組按照寬度由小到大排序，排序同時珊肃，對于寬度相同的項荣刑，根據(jù)高度由大到小排序。
假如我們?nèi)韵穹椒ㄒ灰粯勇浊牵瑑H針對寬度排序厉亏。那么對于形如
和
的兩項，由于
為了規(guī)避上述的問題蔗喂，我們對寬度相等的兩個矩形忘渔，使用高度降序排序，這樣一來缰儿，上述問題的排列將變成：
畦粮。在我們計算最長上升子序列時，由于
，也就不會出現(xiàn)“錯誤套娃”宣赔。
- 排序完畢后预麸，提取出所有的h，形成一個新的數(shù)組儒将。對新的數(shù)組執(zhí)行“最長上升子序列”問題的求解:
- 設(shè)
1. 當(dāng)dp[i] = max(dp[i], dp[j] + 1)
2. 當(dāng)信封
- 轉(zhuǎn)移方程：dp[i] = max(dp[j]) + 1 (j ∈ [0, i) 且信封j比信封i高度嚴格大) -
初始狀態(tài):
-
-
-
返回值:
- 返回
- 返回
復(fù)雜度分析
時間復(fù)雜度
空間復(fù)雜度
快樂小視頻
具體代碼
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
// 首先執(zhí)行排序，按照寬度排序勺美，小的在前大的在后
sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b){
if(a[0] == b[0]){
// 對于寬度相等的信封递胧，根據(jù)高度逆序碑韵，大的在前小的在后
return a[1] > b[1];
}
return a[0] < b[0];
});
// 預(yù)開空間,設(shè)初始值為1,即僅包含當(dāng)前信封
vector<int> dp(n, 1);
int ans = 0;
// 計算最長上升子序列
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(envelopes[j][1] < envelopes[i][1]){
// 如果h嚴格升序赡茸，嘗試更新dp[i]
dp[i] = max(dp[i], dp[j] + 1);
}
}
// 嘗試更新最大值ans
ans = max(ans, dp[i]);
}
return ans;
}
};
比起方法一，有一定優(yōu)化祝闻，但是優(yōu)化效果仍然有限占卧，使用C++提交的運行時間是1004 ms。
仍然是一個 的解決方法
方法三：維護單增序列
思路
更換想法联喘，對方法二中最長上升子序列問題的求解做優(yōu)化华蜒，不再維護長度為 的
數(shù)組，改為維護一條最長遞增序列豁遭。
-
狀態(tài)定義:
-
的最長上升子序列叭喜，第
-
-
狀態(tài)轉(zhuǎn)移:
- 同方法二蓖谢，首先對整個數(shù)組按照寬度由小到大排序捂蕴，排序同時，對于寬度相同的項闪幽，根據(jù)高度由大到小排序啥辨。
- 排序完畢后，提取出所有的h盯腌，形成一個新的數(shù)組溉知。對新的數(shù)組執(zhí)行“最長上升子序列”問題的求解:
-
遍歷
區(qū)間，對每一個值
，判斷
-
當(dāng)
：使用
-
當(dāng)
：使用
-
當(dāng)
為什么可以這樣做舌劳？：假設(shè)當(dāng)前
這翻譯過來是：- 存在一條上升子序列玫荣，長度為1蒿囤，且以1為結(jié)尾；
- 存在一條上升子序列崇决，長度為2材诽，且以3為結(jié)尾；
- 存在一條上升子序列恒傻，長度為3脸侥，且以6為結(jié)尾。
假設(shè)此時來了個新的值4盈厘，顯然的睁枕，可以在長度為2且末尾為3的那條上升子序列后，再添加一個4沸手，形成一條長度為3外遇，且以4為結(jié)尾的上升子序列。
同時更新額外需要注意的是：
- 存在一條上升子序列妄帘，長度為1，且以1為結(jié)尾把敢；
- 存在一條上升子序列寄摆，長度為2，且以2為結(jié)尾修赞；
- 存在一條上升子序列婶恼，長度為3桑阶，且以6為結(jié)尾。
- 轉(zhuǎn)移方程：dp[index] = x (index為第一個大于x的值所在位置)
-
當(dāng)
-
-
初始狀態(tài):
-
值蚣录。
-
-
返回值:
- 返回
- 返回
復(fù)雜度分析
時間復(fù)雜度
空間復(fù)雜度
快樂小視頻
具體代碼
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
// 首先執(zhí)行排序蕉饼，按照寬度排序虐杯，小的在前大的在后
sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b){
if(a[0] == b[0]){
// 對于寬度相等的信封，根據(jù)高度逆序昧港，大的在前小的在后
return a[1] > b[1];
}
return a[0] < b[0];
});
// 預(yù)開空間,初始值為排序后第一個信封的高度
vector<int> dp(1, envelopes[0][1]);
int ans = 0;
// 計算最長上升子序列
// 第0個元素已默認放入dp擎椰，因此從1開始遍歷
for(int i = 1; i < n; i++){
// 搜索合適的更新位置
int j = 0;
for(; j < dp.size(); j++){
// 需要注意，只要不小于當(dāng)前大小创肥，即可更新
if(dp[j] >= envelopes[i][1]){
dp[j] = envelopes[i][1];
break;
}
}
// 如果整個dp列表中达舒，不含有比當(dāng)前h大的值，則擴展dp列表
if(j == dp.size()){
dp.emplace_back(envelopes[i][1]);
}
}
return dp.size();
}
};
比起方法二叹侄，這個方法其實優(yōu)化了很多巩搏，遠不是 的復(fù)雜度，而是
但是假如一開始給定的就是一個層層套娃的合法序列，那么最差時間復(fù)雜度仍然能達到
方法四：二分查找
思路
方法三中，搜索插入位置的過程，用的是 的搜索插入，可以通過二分法淤翔，優(yōu)化到
。
-
狀態(tài)定義:
-
-
-
狀態(tài)轉(zhuǎn)移:
- 同方法二，首先對整個數(shù)組按照寬度由小到大排序得湘，排序同時杖玲，對于寬度相同的項，根據(jù)高度由大到小排序淘正。
- 排序完畢后摆马，提取出所有的h，形成一個新的數(shù)組鸿吆。對新的數(shù)組執(zhí)行“最長上升子序列”問題的求解:
- 遍歷
- **當(dāng)
- **當(dāng)
-
當(dāng)
- **當(dāng)
-
轉(zhuǎn)移方程：
dp[index] = x (index為第一個大于x的值所在位置)
- 遍歷
-
初始狀態(tài):
-
-
-
返回值:
- 返回
- 返回
復(fù)雜度分析
時間復(fù)雜度
空間復(fù)雜度
快樂小視頻
沒啥快樂小視頻了棉磨，看看方法三的得了江掩。
具體代碼
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
// 首先執(zhí)行排序，按照寬度排序乘瓤，小的在前大的在后
sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b){
if(a[0] == b[0]){
// 對于寬度相等的信封环形，根據(jù)高度逆序，大的在前小的在后
return a[1] > b[1];
}
return a[0] < b[0];
});
// 預(yù)開空間,初始值為排序后第一個信封的高度
vector<int> dp(1, envelopes[0][1]);
int ans = 0;
// 計算最長上升子序列
// 第0個元素已默認放入dp衙傀，因此從1開始遍歷
for(int i = 1; i < n; i++){
// 搜索合適的更新位置斟赚，使用二分模板
// 額外引入一個index來記錄滿足條件合法的值
// 有的人的模板中，只有l(wèi)和r兩個變量差油，但是那個邊界條件我總是記不住
// 引入一個新的變量拗军，個人感覺邏輯更明朗
int l = 0, r = dp.size() - 1;
int index = -1;
while(l <= r){
// mid這里用l加一半的形式，不容易溢出int
int mid = l + (r - l) / 2;
if(dp[mid] >= envelopes[i][1]){
// 我們要找的是dp數(shù)組中第一個大于等于當(dāng)前h的位置
// 因此在這里更新index值
index = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
if(index == -1){
dp.emplace_back(envelopes[i][1]);
}
else{
dp[index] = envelopes[i][1];
}
}
return dp.size();
}
};
C++寫到這里蓄喇，差不多就是40-50 ms了发侵，比方法一快了不老少，心滿意足妆偏。
寫在最后
延伸擴展問題
簡化到一維：300. 最長遞增子序列
擴展到三維：面試題 08.13. 堆箱子
加油熹熹坨坨刃鳄！
