[leetcode] 354. Russian Doll Envelopes

本文主要是介绍[leetcode] 354. Russian Doll Envelopes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.

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]).

我的代码

俄国沙皇问题
1.排序策略：假定二元组记为(a,b)，先对a升序排列，当a相同时对b降序排列；
2.排序后只用看b, b的最长不降子序列就是最终的结果；
3.维持一个有效区ends，ends[i]记录b中长度为i+1的最长不降子序列的最小末尾；
注意：在本题中，当拿出的b中的值与ends中的某个值相等时，应该将其放入ends中与其相等的值的位置处，故这个时候应该更新r而不是l。
（更多见算法学习中的笔记）

class Solution {
public:#define max(a,b) a>b?a:b static bool cmp(pair<int, int> env1, pair<int, int> env2){if (env1.first!= env2.first)return env1.first<env2.first;elsereturn env1.second > env2.second;}int maxEnvelopes(vector<pair<int, int> >& envelopes) {if (envelopes.empty()){return 0;}else{sort(envelopes.begin(), envelopes.end(), cmp);int len=envelopes.size();vector<int> ends;ends.resize(len);ends[0]=envelopes[0].second;int l=0, r=0;int Right=0;for (int i=1; i<len; i++){l=0;r=Right;while(l<=r){int ind=(l+r)/2;    if (envelopes[i].second > ends[ind]){l=ind+1;}else{r=ind-1;}}Right=max(Right,l);ends[l]=envelopes[i].second;}return Right+1;}}
};