LeetCode 354. 俄罗斯套娃信封问题

Categories:

题目描述
思路分析
1. 解法一：排序 + 最长递增子序列（推荐）
相似题目

题目描述

✅ 354. 俄罗斯套娃信封问题

思路分析

解法一：排序 + 最长递增子序列（推荐）

核心思路：

先按宽度升序、宽度相同按高度降序排序，避免宽度相同的信封被重复套入。

在高度序列上求最长递增子序列（LIS），即最大可嵌套数量。

使用二分维护 tails，将 LIS 优化到 O(n log n)。

复杂度分析：

时间复杂度：O(n log n)，其中 n 为信封数量。

空间复杂度：O(n)，tails 数组占用。

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return b[1] - a[1];
        });

        int[] tails = new int[envelopes.length];
        int size = 0;

        // 对高度求 LIS
        for (int[] env : envelopes) {
            int h = env[1];
            int l = 0;
            int r = size;
            while (l < r) {
                int m = l + (r - l) / 2;
                if (tails[m] < h) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            tails[l] = h;
            if (l == size) {
                size++;
            }
        }

        return size;
    }
}

import "sort"

func maxEnvelopes(envelopes [][]int) int {
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] != envelopes[j][0] {
            return envelopes[i][0] < envelopes[j][0]
        }
        return envelopes[i][1] > envelopes[j][1]
    })

    tails := make([]int, 0, len(envelopes))

    // 对高度求 LIS
    for _, env := range envelopes {
        h := env[1]
        l, r := 0, len(tails)
        for l < r {
            m := l + (r-l)/2
            if tails[m] < h {
                l = m + 1
            } else {
                r = m
            }
        }
        if l == len(tails) {
            tails = append(tails, h)
        } else {
            tails[l] = h
        }
    }

    return len(tails)
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	LIS
1289. 下降路径最小和 II	困难	DP
646. 最长数对链	中等	LIS
406. 根据身高重建队列	中等	排序
435. 无重叠区间	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/33209766