Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream

1. The subject

Give you a two-dimensional integer array envelopes, where envelopes[I]=[wi,hi]envelopes[I]=[w_i, h_i]envelopes[I]=[wi,hi] represents the width and height of the third envelope.

When the width and height of another envelope are larger than this one, this envelope can be put into another envelope, like a Russian nesting doll.

Please calculate the maximum number of envelopes that can make up a group of matryoshka envelopes (i.e. one envelope can be placed inside another envelope).

Note: Rotating the envelope is not allowed.

Example 1: input: envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]] output: 3: most of the envelope number 3, combination is: [2, 3] = > [5, 4] = > [6, 7]. Example 2: Input: envelopes = [[1,1],[1,1]] Output: 1Copy the code

2.

This problem can be regarded as a variant of the Longes Increasing Subsequence (LIS), because it is clear that each legal nesting is large and small, equivalent to finding a longest Increasing Subsequence whose length is the maximum number of envelopes that can be nested. However, the difficulty lies in that the standard LIS algorithm can only look for the oldest sequence in the array, while our envelope is represented by a two-dimensional number pair like (W, H). How to apply the LIS algorithm?

The reader might think of calculating the area by w×hw ×hw × H, and then performing the standard LIS algorithm for the area. But if you think about it a little bit, you can see that this doesn’t work, like 1 × 10 is bigger than 3 × 3, but obviously these two envelopes can’t be nested into each other.

So since they’re all varieties, can we still sort them?

The width WWW is sorted in ascending order first, and if the WWW is the same, the height HHH is sorted in descending order. Then, all HHH is taken as an array, and the length of LIS is calculated on this array.

Then look for the longest increasing subsequence on HHH:

This subsequence is the optimal nesting scheme. The key to this solution is that for pairs with the same width W, the height h is sorted in descending order. Since two envelopes of the same width cannot contain each other, reverse sorting ensures that at most one of the pairs with the same W is selected.

class Solution { public: int maxEnvelopes(vector<vector<int>>& envelopes) { int n = envelopes.size(); // Sort by width Sort (envelopes.begin(), envelopes. End (), [](vector<int>& a, vector<int>& b){if(a[0] == b[0]){// For envelopes of equal width, Return a[1] > b[1]; return a[1] > b[1]; } return a[0] < b[0]; }); Vector <int> dp(1, envelopes[0][1]); vector<int> dp(1, envelopes[0][1]); int ans = 0; For (int I = 1; for(int I = 1; i < n; I++){// search for the appropriate update location, use binary template // introduce an additional index to record the value of the condition valid // some people in the template, only l and r variables, but I can't remember the boundary condition // introduce a new variable, Int l = 0, r = dp.size() -1; int index = -1; While (l <= r){// mid = l + (r-l) / 2; If (dp[mid] >= envelopes[I][1]){if(dp[mid] >= envelopes[I][1]){if(dp[mid] >= envelopes[I][1]){ r = mid - 1; } else{ l = mid + 1; } } if(index == -1){ dp.emplace_back(envelopes[i][1]); } else{ dp[index] = envelopes[i][1]; } } return dp.size(); }};Copy the code

  • Time complexity O(NlogN)O(NlogN)O(NlogN) O(NlogN) : Sorting requires O(NlogN)O(NlogN)O(NlogN) O(NlogN)O(NlogN)O(NlogN) O(NlogN)O(NlogN)O(NlogN) O(NlogN)O(NlogN)O(NlogN) O(NlogN)O(NlogN)O(NlogN) O(NlogN)O(NlogN)O(NlogN) O(NlogN)O(NlogN)O(NlogN) O(NlogN)O(NlogN)O(NlogN) O

  • Space complexity O(N)O(N)O(N) : Dp lists occupy O(N)O(N)O space.

Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream