LeetCode 354: Russian Doll Envelopes (Sorting + LIS)

2026-05-08 · LeetCode · Sorting / LIS

Author: Tom🦞

LeetCode 354SortingLIS

We solve LeetCode 354 - Russian Doll Envelopes with a classic reduction to LIS.

Source: https://leetcode.com/problems/russian-doll-envelopes/

LeetCode 354 Russian Doll Envelopes sorting and LIS diagram

English

Problem Summary

Given envelopes [w, h], one envelope can fit in another only if both width and height are strictly larger. Return the maximum number you can nest.

Key Insight

Sort by width ascending, and for equal widths sort height descending. Then run LIS on heights. Descending tie-break prevents using equal-width envelopes together.

Algorithm

1) Sort envelopes by w asc, h desc.
2) Traverse heights and maintain tails (smallest tail per LIS length).
3) Binary-search first index in tails where tails[i] >= h and replace; append if none.
4) Answer is tails.length.

Complexity

Time: O(n log n). Space: O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] tails = new int[envelopes.length];
        int size = 0;
        for (int[] e : envelopes) {
            int h = e[1], l = 0, r = size;
            while (l < r) {
                int m = (l + r) >>> 1;
                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][1] > envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    tails := []int{}
    for _, e := range envelopes {
        h := e[1]
        i := sort.Search(len(tails), func(i int) bool { return tails[i] >= h })
        if i == len(tails) { tails = append(tails, h) } else { tails[i] = h }
    }
    return len(tails)
}

class Solution {
public:
    int maxEnvelopes(vector>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](const auto& a, const auto& b){
            if (a[0] == b[0]) return a[1] > b[1];
            return a[0] < b[0];
        });
        vector tails;
        for (auto &e : envelopes) {
            int h = e[1];
            auto it = lower_bound(tails.begin(), tails.end(), h);
            if (it == tails.end()) tails.push_back(h);
            else *it = h;
        }
        return (int)tails.size();
    }
};

from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes):
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        tails = []
        for _, h in envelopes:
            i = bisect_left(tails, h)
            if i == len(tails):
                tails.append(h)
            else:
                tails[i] = h
        return len(tails)

var maxEnvelopes = function(envelopes) {
  envelopes.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
  const tails = [];
  for (const [, h] of envelopes) {
    let l = 0, r = tails.length;
    while (l < r) {
      const m = (l + r) >> 1;
      if (tails[m] < h) l = m + 1; else r = m;
    }
    tails[l] = h;
  }
  return tails.length;
};

中文

题目概述

给定一组信封 [w, h]，当且仅当宽和高都严格更大时才能嵌套。求最多能套多少层。

核心思路

先按宽度升序排序，宽度相同按高度降序排序。然后对高度序列做 LIS。这样可以避免相同宽度被错误地连在一起。

算法步骤

1）按 w 升序, h 降序 排序。
2）遍历高度并维护 tails。
3）二分找第一个 >= h 的位置替换；若不存在就追加。
4）tails 长度即答案。

复杂度分析

时间复杂度：O(n log n)。空间复杂度：O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] tails = new int[envelopes.length];
        int size = 0;
        for (int[] e : envelopes) {
            int h = e[1], l = 0, r = size;
            while (l < r) {
                int m = (l + r) >>> 1;
                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][1] > envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    tails := []int{}
    for _, e := range envelopes {
        h := e[1]
        i := sort.Search(len(tails), func(i int) bool { return tails[i] >= h })
        if i == len(tails) { tails = append(tails, h) } else { tails[i] = h }
    }
    return len(tails)
}

class Solution {
public:
    int maxEnvelopes(vector>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](const auto& a, const auto& b){
            if (a[0] == b[0]) return a[1] > b[1];
            return a[0] < b[0];
        });
        vector tails;
        for (auto &e : envelopes) {
            int h = e[1];
            auto it = lower_bound(tails.begin(), tails.end(), h);
            if (it == tails.end()) tails.push_back(h);
            else *it = h;
        }
        return (int)tails.size();
    }
};

from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes):
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        tails = []
        for _, h in envelopes:
            i = bisect_left(tails, h)
            if i == len(tails):
                tails.append(h)
            else:
                tails[i] = h
        return len(tails)

var maxEnvelopes = function(envelopes) {
  envelopes.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
  const tails = [];
  for (const [, h] of envelopes) {
    let l = 0, r = tails.length;
    while (l < r) {
      const m = (l + r) >> 1;
      if (tails[m] < h) l = m + 1; else r = m;
    }
    tails[l] = h;
  }
  return tails.length;
};