354. Russian Doll Envelopes

Leetcode link

解题思路

本题给了我们一个二维数组，数组的每一个项代表信封的长跟宽，要求我们求出这些信封最多能套几层娃

一个简单的暴力思路是将二维数组元素依照进行升序排序，如果第一位相等则对第二位升序排序

这样一来我们只需要用两个 for 循环再加上一个 dp 数组就能够穷举出所有的可能性，最后选择最大的就好了

代码如下，只是会 TLE：

C++

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int len = envelopes.size();
        int res = 0;
        vector<int> dp(len, 1);
        sort(envelopes.begin(), envelopes.end());
        for(int i=0;i<len;i++) {
            for(int j=0;j<i;j++) {
                if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(dp[i], res);
        }
        return res;
    }
};

Javascript

/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function(envelopes) {
    let len = envelopes.length;
    let dp = new Array(len).fill(1);
    envelopes.sort((a, b) => {
        if(a[0] === b[0]) {
            return a[1] - b[1];
        }
        return a[0] - b[0];
    })

    for(let i=0;i<len;i++) {
        for(let j = 0;j<i;j++) {
            if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1] ){
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
    }
    return Math.max(...dp);
};

既然会 TLE，为什么还要写出来呢？因为上述的解法有优化的空间

具体来说，我们可以基于上述的思路，加上一点二分搜索的操作降低复杂度：

• 首先对二维数组元素的排序规则改为：先对第一位进行升序，如果第一位相等，则对第二位进行降序
• 这样一来，我们就可以保证当数组元素第二位是升序的时候，前面的信封可以被放到后面的信封里

说明：因为元素第一位相同的情况下，第二位为降序；所以如果元素经过排序后的第二位是升序的话，则只可能是因为第一位是越来越大的，这个条件恰好符合可以放进去的约束

如此一来，我们就可以把问题简化成：求排序后的数组元素第二位的最长升序子数组长度

求最长升序子数组，我们可以用二分查找的方法：

• 首先维护一个一维数组 dp，把首元素先放进数组中
• 然后遍历比较之后的元素，如果之后的元素比首元素小，则将新元素替换旧的首元素
• 如果新的元素比 dp 数组中末尾元素还大的话，则 push 新元素进 dp 末尾
• 如果新元素介于首元素与尾元素之间，则用二分搜索找到第一个不小于新元素的元素，且用新元素替换掉它
• 最后我们只需要查看 dp 数组的长度就能够得出最长升序子数组的长度了

具体看代码：

C++

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        vector<int> dp;
        sort(envelopes.begin(), envelopes.end(), [](const vector<int> &a,const vector<int> &b) {
            if(a[0] == b[0]) {
                return a[1] > b[1];
            }
            return a[0] < b[0];
        });

        for(int i = 0;i < envelopes.size();i++) {
            int left = 0, right = dp.size();
            int value = envelopes[i][1];
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(dp[mid] < value) {
                    left  = mid+1;
                }else {
                    right = mid;
                }
            }
            if(right>=dp.size()) {
                dp.push_back(value);
            }else {
                dp[right] = value;
            }
        }
        return dp.size();
    }
};

Javascript

/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function(envelopes) {
    let dp = [];
    envelopes.sort((a, b)=>{
        if(a[0] === b[0]) {
            return b[1] - a[1];
        }
        return a[0] - b[0];
    });
    for(let i=0;i<envelopes.length;i++) {
        let left = 0, right = dp.length;
        let value = envelopes[i][1];
        while(left<right) {
            let mid = left + Math.floor((right-left) / 2);
            if(value > dp[mid]) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        if(right >= dp.length) {
            dp.push(value);
        }else {
            dp[right] = value;
        }
    }
    return dp.length;
};