354. Russian Doll Envelopes

题目 354. Russian Doll Envelopes

思路分析

能否贪心？用优先队列 按长、宽共同排序 先拿到最大的作为cur 看下一个能否嵌入 不能就再看下一个 cur会更新成最新的 cnt++

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length == 0)   return 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
            if(a[0]!=b[0]){
                return b[0]-a[0];
            }else{
                return b[1]-a[1];
            }
        });

        for(int[] env:envelopes){
            pq.offer(env);
        }

        int[] cur = pq.poll();
        int cnt = 1;

        while(!pq.isEmpty()){
            int[] next = pq.poll();
            if(next[0]<cur[0] && next[1]<cur[1]){
                cnt++;
                cur=next;
            }
        }
        return cnt;
    }
}

假设输入是：[[10, 2], [5, 10], [4, 9], [3, 8]]

1. 当前代码执行流程：
   • 排序后 PQ：[10, 2], [5, 10], [4, 9], [3, 8]
   • 取出 cur = [10, 2] (因为它的宽 10 最大)。
   • 取出 next = [5, 10]。判断：5 < 10 (true) 但 10 < 2 (false)。不能放入，丢弃。
   • 取出 next = [4, 9]。判断：4 < 10 (true) 但 9 < 2 (false)。不能放入，丢弃。
   • 取出 next = [3, 8]。判断：3 < 10 (true) 但 8 < 2 (false)。不能放入，丢弃。
   • 最终输出结果：1
2. 正确的最优解：
   • 我们不选那个看起来最大的 [10, 2]。
   • 我们可以选 [5, 10] -> [4, 9] -> [3, 8]。
   • 正确结果：3

结论： 贪心策略在于“只顾眼前最大”。一旦选了一个**“偏科”**的信封（比如特别宽但特别矮的 [10, 2]），它就会把后面所有“瘦高”个子的潜在答案全部卡死。

到这里其实就知道 应该是个dp问题

最长上升子序列模型的二维变种

可以通过巧妙的排序，将二维问题降维成一维问题：

1. 巧妙的排序规则（核心！）

• 按宽度 (\(w\)) 升序排序：保证后面的信封宽度肯定比前面的大（或相等）。
• 如果宽度相同，按高度 (\(h\)) 降序排序：这是一个非常关键的技巧！

为什么要让高度降序？

假设有两个信封 [3, 3] 和 [3, 4]。

• 如果我们按高度升序排：[3, 3], [3, 4]。在计算 LIS 时，3 和 4 会形成递增序列，导致我们误判 [3, 3] 可以放入 [3, 4]，但这在物理上是不可能的（宽度相同不能套娃）。
• 如果我们按高度降序排：[3, 4], [3, 3]。在计算 LIS 时，3 无法接在 4 后面增加长度，从而避免了同一宽度下选择多个信封的情况。

2. 一维 LIS

排序后，我们只需要对 高度 (\(h\)) 数组求 最长递增子序列 的长度即可。因为宽度已经是升序的了，只要高度递增，信封就能套进去。

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        if(n==0)    return 0;
        Arrays.sort(envelopes,(a,b)->{
            if(a[0]==b[0]){
                return b[1]-a[1];//h降序
            }else{
                return a[0]-b[0];//w升序
            }
        });

        int[] f = new int[n];
        Arrays.fill(f,1);
        int res = 1;

        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                // 因为已经按宽度排好序了(且同宽按高度降序)，
                // 所以只要 envelopes[j][1] < envelopes[i][1]，
                // 就意味着 envelopes[j] 一定能放进 envelopes[i]
                if(envelopes[j][1]<envelopes[i][1]){
                    f[i]=Math.max(f[i],f[j]+1);
                }
            }
            res=Math.max(res,f[i]);
        }
        return res;
    }
}

注意：由于 \(N\) 高达 \(10^5\)，普通的 \(O(N^2)\) DP 解法会超时，必须使用 二分查找优化 的贪心 LIS 解法，复杂度为 \(O(N \log N)\)。

代码实现

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        if(n==0)    return 0;
        Arrays.sort(envelopes,(a,b)->{
            if(a[0]==b[0]){
                return b[1]-a[1];//h降序
            }else{
                return a[0]-b[0];//w升序
            }
        });


        int[] f = new int[n];
        int res = 0;

        for (int[] env : envelopes) {
            int h = env[1];
            
            // 贪心策略：
            // 情况 1: 如果当前高度 h 比 f 数组中最大的元素（最后一个）还要大，直接追加
            if (res == 0 || h > f[res - 1]) {
                f[res] = h;
                res++;
            } 
            // 情况 2: 否则，二分找到第一个 >= h 的位置进行替换
            else {
                // 在 f 数组的 [0, res-1] 范围内查找
                int index = Search(f, 0, res - 1, h);
                f[index] = h;
            }
        }

        return res;
    }

    private int Search(int[] nums, int l, int r, int k) {
        while (l < r) {
            int m = (l + r) >>> 1;
            if (nums[m] >= k) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return r;
    }

}

同类题型

视频讲解