第三章：信封嵌套问题

labuladong 信封嵌套问题

354. 俄罗斯套娃信封问题

• 先对宽度（第一个数）进行升序排序，宽度相同时，对高度（第二个数）降序排序 envelopes=sorted(envelopes,key=lambda x:(x[0],-x[1]))
• 然后对高度求最长上升子序列

这个解法的关键在于，对于宽度 w 相同的数对，要对其高度 h 进行降序排序。因为两个宽度相同的信封不能相互包含的，逆序排序保证在 w 相同的数对中最多只选取一个。

class Solution(object):
    def maxEnvelopes(self, envelopes):
        # w升序，w相同时h降序
        envelopes=sorted(envelopes,key=lambda x:(x[0],-x[1]))
        h=[i[1] for i in envelopes]# 取h
        res=self.lengthOfLIS(h) # 调用函数
        return res

    # 最长上升子序列函数
    def lengthOfLIS(self,nums):
        if not nums:
            return 0
        dp = [1 for _ in range(len(nums))]
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

//#include <vector>
//#include <iostream>
//#include <algorithm>
//using namespace std;

class Solution {
public:
    //求最大递增子序列的长度
    int lengthOfLIS(vector<int> &nums) {
        vector<int> dp(nums.size(), 1);
        for (int i = 1; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }

    int maxEnvelopes(vector<vector<int>> &envelopes) {
        // 宽度升序排列，如果宽度相同，则高度降序排列
        // 用到了lambda表达式
        sort(envelopes.begin(), envelopes.end(), [](vector<int> &a, vector<int> &b) {
            if (a[0] == b[0]) {
                return a[1] > b[1];// 如果宽度相同，则高度降序排列
            }
            return a[0] < b[0]; // 宽度升序排列
        });
        // 把动态数组的第二列（即：高度）取出来
        vector<int> h;
        for (auto &item:envelopes) {
            h.push_back(item[1]);
        }
        // 求高度对应的最长递增子序列
        int res = lengthOfLIS(h);
        return res;
    }
};

//int main(){
//    vector<vector<int>> envelops={{5,4},{6,4},{6,7},{2,3}};
//    Solution so;
//    cout<<so.maxEnvelopes(envelops)<<endl; // 3
//}