354. Russian Doll Envelopes
1. Description
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).
2. Example
Example 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]).
Example 2:
Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
3. Note
- You cannot rotate an envelope.
4. Constraints
- 1 <= envelopes.length <= 5000
- envelopes[i].length == 2
- 1 <= wi, hi <= $10^4$
5. Solutions
My Accepted Solution
n = i_nums.size()
Time complexity: O(nlogn)
Space complexity: O(n)
reference 300. Longest Increasing Subsequence
class Solution
{
public:
int maxEnvelopes(vector<vector<int>> &m_envelopes)
{
// there is a key to simpify the question to Leetcode 300
// we could turn the 2 diversion problem to 1 diversion by sorting 1 diversion
// and let the other diversion to as Leetcode 300
// so, we sort the width of envelops, but there could be some envelopes have the same height
// then, we may select more than on envelops with the same width, which is invalid
// so when we sort envelopes, we sort the height by devrease order
// so, if we select any envelope with a given width, its later envelopes' height is more little,
// which can't hold the selected one
// so, we could not select two envelopes with the same width
sort(m_envelopes.begin(), m_envelopes.end(), [](vector<int> left, vector<int> right) {
return left.front() == right.front() ? left.back() > right.back() : left.front() < right.front();
});
int longestLength = 1;
vector<int> minLastValueOfLength(m_envelopes.size() + 1);
minLastValueOfLength[longestLength] = m_envelopes.front().back();
for (int i = 1; i < m_envelopes.size(); i++)
{
if (m_envelopes[i].back() > minLastValueOfLength[longestLength])
{
longestLength++;
minLastValueOfLength[longestLength] = m_envelopes[i].back();
}
else
{
auto iter = lower_bound(minLastValueOfLength.begin() + 1, minLastValueOfLength.begin() + longestLength + 1, m_envelopes[i].back());
if (iter == minLastValueOfLength.begin() + longestLength + 1)
minLastValueOfLength[1] = m_envelopes[i].back();
else
*iter = m_envelopes[i].back();
}
}
return longestLength;
}
};