leetcode Russian Doll Envelopes

leetcode Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

传送门:leetcode Russian Doll Envelopes

题意:给定一些信封的宽和长,当且仅当信封x的宽和长均小于另一个信封y时,x可以装入y,求最多可以嵌套的装几个?

思路: 看到就知道是求LIS了(最大上升子序列),不明白为啥会是hard难度。

求LIS可以直接简单的dp,设dp[i]为以i为结尾的LIS长度,则dp[i] = max(0,dp[j] | j<i && A[j] < A[i]) + 1

复杂度为O(n^2),但可以优化到O(nlogn),排序然后二分。

本题需要注意排序的时候要注意第一项相同的情况下,第二项的顺序。

 

 

C++

 

Python

 

 

本题是leetcode 354  Russian Doll Envelopes 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Russian Doll Envelopes
本文地址:https://www.hrwhisper.me/leetcode-russian-doll-envelopes/

听说长得好看的已经打赏了

Leetcode , , . permalink.

5 thoughts on “leetcode Russian Doll Envelopes

  1. 这个题目有个follow up就是长宽可以互换,请问这该怎么做呢
    比如[1,2][5,2][3,6] 在这种抢矿下就是[1,2]->[2,5]->[3,6]了

    • 因为正序的话,将会把第一项相同的情况继续算入,如[1,2] [3,5] [3,6]正序排,LIS就是256 输出答案3,但是是错误的。 如果第二个逆序 则[1,2] [3,6] [3,5] ,要么26 要么 25答案正确。

Leave a Reply

Your email address will not be published. Required fields are marked *