返回介绍

solution / 0300-0399 / 0354.Russian Doll Envelopes / README

发布于 2024-06-17 01:04:01 字数 3998 浏览 0 评论 0 收藏 0

354. 俄罗斯套娃信封问题

English Version

题目描述

给你一个二维整数数组 envelopes ,其中 envelopes[i] = [wi, hi] ,表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。

注意:不允许旋转信封。

 

示例 1:

输入:envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出:3
解释:最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2:

输入:envelopes = [[1,1],[1,1],[1,1]]
输出:1

 

提示:

  • 1 <= envelopes.length <= 105
  • envelopes[i].length == 2
  • 1 <= wi, hi <= 105

解法

方法一:贪心 + 二分查找

时间复杂度 O(nlogn)。

class Solution:
  def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    d = [envelopes[0][1]]
    for _, h in envelopes[1:]:
      if h > d[-1]:
        d.append(h)
      else:
        idx = bisect_left(d, h)
        if idx == len(d):
          idx = 0
        d[idx] = h
    return len(d)
class Solution {
  public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (a, b) -> { return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]; });
    int n = envelopes.length;
    int[] d = new int[n + 1];
    d[1] = envelopes[0][1];
    int size = 1;
    for (int i = 1; i < n; ++i) {
      int x = envelopes[i][1];
      if (x > d[size]) {
        d[++size] = x;
      } else {
        int left = 1, right = size;
        while (left < right) {
          int mid = (left + right) >> 1;
          if (d[mid] >= x) {
            right = mid;
          } else {
            left = mid + 1;
          }
        }
        int p = d[left] >= x ? left : 1;
        d[p] = x;
      }
    }
    return size;
  }
}
class Solution {
public:
  int maxEnvelopes(vector<vector<int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
      return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
    });
    int n = envelopes.size();
    vector<int> d{envelopes[0][1]};
    for (int i = 1; i < n; ++i) {
      int x = envelopes[i][1];
      if (x > d[d.size() - 1])
        d.push_back(x);
      else {
        int idx = lower_bound(d.begin(), d.end(), x) - d.begin();
        if (idx == d.size()) idx = 0;
        d[idx] = x;
      }
    }
    return d.size();
  }
};
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[j][1] < envelopes[i][1]
  })
  n := len(envelopes)
  d := make([]int, n+1)
  d[1] = envelopes[0][1]
  size := 1
  for _, e := range envelopes[1:] {
    x := e[1]
    if x > d[size] {
      size++
      d[size] = x
    } else {
      left, right := 1, size
      for left < right {
        mid := (left + right) >> 1
        if d[mid] >= x {
          right = mid
        } else {
          left = mid + 1
        }
      }
      if d[left] < x {
        left = 1
      }
      d[left] = x
    }
  }
  return size
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文