Clean C++ 11 Implementation with Explaination refered from @kamyu104


  • 3

    It is easy to relate this problem with the previous LIS problem. But how to solve it under the 2 dimensional cases. The key ideas lay at that how we deal with the equal width but different hight cases.

    A clever solution is to sort the pair<int,int> array according the width, if the width is equal, just sort by the height reversely.

    Then we can get the following solutions :

    class Solution {
    public:
        int maxEnvelopes(vector<pair<int, int>>& envelopes) {
            int size_ = envelopes.size();
            if(size_ < 2)  return size_; 
            sort(envelopes.begin(), envelopes.end(), 
                [](const pair<int, int>& a, const pair<int, int>& b) {
                    if(a.first == b.first) {
                        return a.second > b.second;
                    }
                    else {
                        return a.first < b.first;
                    }
                });
            /** find the LIS of the height, as we have filtered the width equal cases **/
            vector<int> result;
            for (const auto& iter : envelopes) {
                const auto target = iter.second;
                auto cur = lower_bound(result.begin(), result.end(), target);
                if (cur == result.end()) {
                    result.emplace_back(target);
                } else {
                    *cur = target;
                }
            }
            return result.size();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.