每個信封有寬
w與高h，只有當一個信封的寬與高都嚴格大於另一個時才能套入。求最多能套幾層（俄羅斯娃娃）。
Example:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3（[2,3] → [5,4] → [6,7]）
Intuition
TIP
核心思路：先把寬度排序，問題就化為對高度求「最長嚴格遞增子序列（LIS）」。關鍵小技巧：寬度相同時，高度要遞減排序，避免同寬被誤算成可巢狀。
- 排序鍵：寬度升序；寬度相同時高度降序
- 為何高度降序：同寬不能互套，降序確保同寬中最多只取一個進 LIS
- 排序後對高度跑 LIS（二分版）得
O(n log n)
Approaches
1. Sort + O(n²) DP LIS — O(n²) / O(n)
- Idea: 排序後對高度做標準 LIS DP
- Time:
O(n²)- 大 n 會 TLE，僅作理解 - Space:
O(n)
class Solution {
fun maxEnvelopes(envelopes: Array<IntArray>): Int {
envelopes.sortWith(compareBy({ it[0] }, { -it[1] }))
val n = envelopes.size
val dp = IntArray(n) { 1 }
var ans = 0
for (i in 0 until n) {
for (j in 0 until i) {
if (envelopes[j][1] < envelopes[i][1]) dp[i] = maxOf(dp[i], dp[j] + 1)
}
ans = maxOf(ans, dp[i])
}
return ans
}
}⭐ 2. Sort + LIS Binary Search (patience) — O(n log n) / O(n)
- Idea: 對高度跑二分版 LIS，維護 tails 陣列
- Time:
O(n log n)- 排序 + 每個元素二分 - Space:
O(n)
class Solution {
fun maxEnvelopes(envelopes: Array<IntArray>): Int {
// 寬升序；同寬高降序（避免同寬被當成可套）
envelopes.sortWith(compareBy({ it[0] }, { -it[1] }))
val tails = ArrayList<Int>() // tails[k] = 長度 k+1 的遞增子序列的最小結尾高度
for (e in envelopes) {
val h = e[1]
var lo = 0; var hi = tails.size
while (lo < hi) {
val mid = (lo + hi) ushr 1
if (tails[mid] < h) lo = mid + 1 else hi = mid
}
if (lo == tails.size) tails.add(h) else tails[lo] = h
}
return tails.size
}
}🔑 Takeaways
- Pattern: 二維偏序化為一維 LIS——固定一維（排序），對另一維求 LIS
- Key trick: 同寬高度降序是整題精髓（否則
[6,4],[6,7]會被誤算成可套）；LIS 二分版把O(n²)壓到O(n log n)。是 300 LIS 的進階應用