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++

bool cmp(pair<int,int>&x, pair<int, int>&y) {
	return x.first != y.first ? x.first < y.first : x.second > y.second;
}

class Solution {
public:
	int maxEnvelopes(vector<pair<int, int>>& envelopes) {
		int n = envelopes.size();
		if (!n) return 0;
		sort(envelopes.begin(), envelopes.end(), cmp);
		vector<int> dp(n, 1),g(n+1, 0x7fffffff);
		for (int i = 0; i < n; i++) {
			int k = lower_bound(++g.begin(), g.end(), envelopes[i].second) - g.begin();
			dp[i] = k;
			g[k] = envelopes[i].second;
		}
		int ans = 0;
		for (int i = 0; i < n; i++) ans = max(ans, dp[i]);
		return ans;
	}
};

 

Python

class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """

        def lower_bound(arrays, L, R, x):
            while L < R:
                mid = (L + R) >> 1
                if x <= arrays[mid]:
                    R = mid
                else:
                    L = mid + 1
            return L

        if not envelopes: return 0
        A = sorted(envelopes, lambda x, y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1])
        n = len(A)
        dp = [1] * n
        g = [0x7fffffff] * (n + 1)
        for i in xrange(n):
            k = lower_bound(g, 1, n, A[i][1])
            dp[i] = k
            g[k] = A[i][1]
        return max(dp)

 

本题是leetcode 354  Russian Doll Envelopes 题解

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