[Leetcode]354. Russian Doll Envelopes(C++)

题目描述

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

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.

Return the maximum number of envelopes can you Russian doll (i.e., put one inside the other).

例子

例子 1

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

例子 2

Input: envelopes = [[1,1],[1,1],[1,1]] Output: 1

Note

You cannot rotate an envelope.

Constraints

1 <= envelopes.length <= 5000

envelopes[i].length == 2

1 <= wi, hi <= 10^4

解题思路

这道题是 [Leetcode]300. Longest Increasing Subsequence(C++) 的二维版本，本质上要求是要求我们返回一个子组合，其中第一个元素和第二个元素组成的序列各自都是递增的。我们可以将数组按每个元素的第一个数字大小进行排序，排序之后我们会得到一个在第一个元素是递增的数组，因此问题就转变成我们要在这个数组中获取最长的子序列，要求第二个数组元素是递增的，因此可以用 [Leetcode]300. Longest Increasing Subsequence(C++) 的方法来求解，这里要注意一点，由于有可能存在第一个元素相同的情况，我们需要考虑以下情况：

给定两个数组，[a. b1] 和 [a, b2] 其中 b1 < b2

按照题目的要求： [a, b1] 是不能放进 [a, b2] 的（由于宽度相同），因此在排序的时候我们需要将 [a, b2] 放在前面，自动筛选掉可能会出现的 [[a, b1], [a, b2]] 的情况。

两种方法代码如下：

动态规划

#include <algorithm>
#include <vector>
class Solution {
public:
    int maxEnvelopes(std::vector<std::vector<int>>& envelopes) {
        std::vector<int> maxNumsEnvelopes(envelopes.size(), 1);
        std::sort(
            envelopes.begin(), envelopes.end(),
            [](const std::vector<int>& left, const std::vector<int>& right) {
                if (left[0] != right[0]) {
                    return left[0] < right[0];
                } else {
                    return left[1] > right[1];
                }
            });
        int result = 1;
        for (int i = 1; i < envelopes.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][0] > envelopes[j][0] &&
                    envelopes[i][1] > envelopes[j][1]) {
                    maxNumsEnvelopes[i] =
                        std::max(maxNumsEnvelopes[i], maxNumsEnvelopes[j] + 1);
                    result = std::max(result, maxNumsEnvelopes[i]);
                }
            }
        }

        return result;
    }
};

时间复杂度: O(n^2)
空间复杂度: O(n)

二分查找

#include <algorithm>
#include <vector>
class Solution {
public:
    int maxEnvelopes(std::vector<std::vector<int>>& envelopes) {
        std::sort(
            envelopes.begin(), envelopes.end(),
            [](const std::vector<int>& left, const std::vector<int>& right) {
                if (left[0] != right[0]) {
                    return left[0] < right[0];
                } else {
                    return left[1] > right[1];
                }
            });
        std::vector<int> minHeight{};
        for (const std::vector<int>& envelope : envelopes) {
            int index = binary_search(minHeight, envelope[1]);
            if (index == -1) {
                continue;
            } else if (index == minHeight.size()) {
                minHeight.push_back(envelope[1]);
            } else {
                minHeight[index] = envelope[1];
            }
        }

        return minHeight.size();
    }

private:
    int binary_search(const std::vector<int>& nums, int target) {
        if (nums.empty() || nums.back() < target) return nums.size();
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
};

时间复杂度: O(nlog n)
空间复杂度: O(n)

GitHub 代码同步地址： 354.RussianDollEnvelopes.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions