Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to solve the Russian doll envelope problem with leetcode". The explanation content in this article is simple and clear, and it is easy to learn and understand. Please follow the ideas of Xiaobian to study and learn "how to solve the Russian doll envelope problem with leetcode" together.

I. Content of the topic

Given some envelopes marked with width and height, width and height appear as integer pairs (w, h). When the other envelope is wider and taller than this envelope, this envelope can fit into another envelope, like a Russian doll.

Please calculate the maximum number of envelopes that can form a "Russian doll" envelope (i.e., one envelope can be placed inside another envelope).

Description:

Rotating envelopes is not allowed.

Examples:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]

Output: 3

Explanation: The maximum number of envelopes is 3, and the combination is: [2,3] => [5,4] => [6,7].

II. Solution ideas

Sort envelopes in ascending order of width w, and then in descending order of height h for envelopes of the same width w;

The purpose of height descending order is to store the height h in an array of aligned envelopes and store the height h of envelopes by binary insertion (LIS: longest rising (not falling) subsequence);

If the envelope width w is the same, then choose the height h is small, otherwise it will store envelopes of different heights h with the same width w, but the width w cannot be the same, so the height h should be reduced, so that the height h can be updated.

3. Code from bisect import bisect_leftclass Solution: def LIS(self, nums): res = [] for num in nums: index = bisect_left(res, num) if index == len(res): res.append(num) else: res[index] = num return len(res) def maxEnvelopes(self, envelopes: list) -> int: envelopes.sort(key=lambda x: (x[0], -x[1])) print(envelopes) return self.LIS([envelope[1] for envelope in envelopes])if __name__ == '__main__': s = Solution() envelopes = [[4, 5], [4, 6], [6, 7], [2, 3], [1, 1]] ans = s.maxEnvelopes(envelopes) print(ans) Thank you for your reading. The above is the content of "How to solve the Russian doll envelope problem with leetcode". After studying this article, I believe everyone has a deeper understanding of how to solve the Russian doll envelope problem with leetcode. The specific use situation still needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.