题解 | 信封嵌套

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxEnvelopes(vector<vector<int>>& envelopes) {
    // 按宽度升序排序，宽度相同时按长度降序排序
    sort(envelopes.begin(), envelopes.end(), 
        [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });
    
    // 在长度上找最长递增子序列
    vector<int> dp;
    for(const auto& envelope : envelopes) {
        int height = envelope[1];
        auto it = lower_bound(dp.begin(), dp.end(), height);
        if(it == dp.end()) {
            dp.push_back(height);
        } else {
            *it = height;
        }
    }
    
    return dp.size();
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> envelopes(n, vector<int>(2));
    for(int i = 0; i < n; i++) {
        cin >> envelopes[i][0] >> envelopes[i][1];
    }
    cout << maxEnvelopes(envelopes) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int maxEnvelopes(int[][] envelopes) {
        // 按宽度升序排序，宽度相同时按长度降序排序
        Arrays.sort(envelopes, (a, b) -> 
            a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        
        // 在长度上找最长递增子序列
        int[] dp = new int[envelopes.length];
        int len = 0;
        for(int[] envelope : envelopes) {
            int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
            if(index < 0) {
                index = -(index + 1);
            }
            dp[index] = envelope[1];
            if(index == len) {
                len++;
            }
        }
        
        return len;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] envelopes = new int[n][2];
        for(int i = 0; i < n; i++) {
            envelopes[i][0] = sc.nextInt();
            envelopes[i][1] = sc.nextInt();
        }
        System.out.println(maxEnvelopes(envelopes));
        sc.close();
    }
}

def max_envelopes(envelopes):
    # 按宽度升序排序，宽度相同时按长度降序排序
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    
    # 在长度上找最长递增子序列
    dp = []
    for _, height in envelopes:
        left, right = 0, len(dp)
        while left < right:
            mid = (left + right) // 2
            if dp[mid] < height:
                left = mid + 1
            else:
                right = mid
        if left == len(dp):
            dp.append(height)
        else:
            dp[left] = height
    
    return len(dp)

n = int(input())
envelopes = []
for _ in range(n):
    w, h = map(int, input().split())
    envelopes.append([w, h])
print(max_envelopes(envelopes))