602. Russian Doll Envelopes
超时，
但是不理解二分的方法。就这样吧
https://www.cnblogs.com/grandyang/p/4938187.html
和longest increasing subsequence相似的
class Solution { public: /* * @param envelopes: a number of envelopes with widths and heights * @return: the maximum number of envelopes */ static bool cmp1(const pair<int, int> a, const pair<int, int> b){ return a.first < b.first || (a.first == b.first && a.second > b.second); } int maxEnvelopes(vector<pair<int, int>>& envelopes) { // write your code here const int size = envelopes.size(); if(size == 0){ return 0; } sort(envelopes.begin(), envelopes.end(), cmp1); vector<int> f(size, 1); f[0] = 1; int res = 1; for(int i = 1; i < size; i++){ for(int j = i - 1; j >= 0; j--){ if(envelopes[i].second > envelopes[j].second){ f[i] = max(f[i], f[j] + 1); } } res = max(f[i], res); } return res; } };
但是不理解二分的方法。就这样吧
https://www.cnblogs.com/grandyang/p/4938187.html
和longest increasing subsequence相似的
class Solution { public: /* * @param envelopes: a number of envelopes with widths and heights * @return: the maximum number of envelopes */ static bool cmp1(const pair<int, int> a, const pair<int, int> b){ return a.first < b.first || (a.first == b.first && a.second > b.second); } int maxEnvelopes(vector<pair<int, int>>& envelopes) { // write your code here const int size = envelopes.size(); if(size == 0){ return 0; } sort(envelopes.begin(), envelopes.end(), cmp1); vector<int> f(size, 1); f[0] = 1; int res = 1; for(int i = 1; i < size; i++){ for(int j = i - 1; j >= 0; j--){ if(envelopes[i].second > envelopes[j].second){ f[i] = max(f[i], f[j] + 1); } } res = max(f[i], res); } return res; } };
Comments
Post a Comment