俄罗斯信封套娃问题-二维最长递增子序列

354. 俄罗斯套娃信封问题 - 力扣（LeetCode）

Solution

对一个维度从小到大排序，然后对另外一个维度求最长上升子序列即可。

class Solution {
public:struct node {int w, h;node(int w, int h) {this->w = w;this->h = h;}};static bool cmp(node a, node b) {return a.w < b.w || (a.w == b.w && a.h > b.h);}int maxEnvelopes(vector<vector<int>>& envelopes) {int n = envelopes.size();int ans = 0;vector<node>nums1;// vector<node>nums2;for (vector<int>x : envelopes) {nums1.emplace_back(node(x[0], x[1]));// nums2.emplace_back(node(x[1], x[0]));}sort(nums1.begin(), nums1.end(), cmp);// sort(nums2.begin(), nums2.end(), cmp);// ans = max(lengthOfLIS(nums1), lengthOfLIS(nums2));ans=lengthOfLIS(nums1);return ans;}int lengthOfLIS(vector<node>& nums) {int n = nums.size();vector<int>ends;ends.push_back(nums[0].h);for (int i = 1; i < n; ++i) {int cur = nums[i].h;int index = bs(ends, cur);if (index == -1) {ends.push_back(cur);}else {ends[index] = cur;}}return ends.size();}int bs(vector<int>& nums, int v) {int l = 0, r = nums.size() - 1;int ans = -1;while (l <= r) {int mid = (l + r) >> 1;if (nums[mid] >= v) {ans = mid;r = mid - 1;}else {l = mid + 1;}}return ans;}
};