binarySearch on LIS

一） LeetCode 300. 最长递增子序列

1 题目描述

• 题目链接：300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例1：

输入: nums = [10,9,2,5,3,7,101,18]
输出: 4

示例2：

输入: nums = [0,1,0,3,2,3]
输出: 4

示例3：

输入: nums = [7,7,7,7,7,7,7]
输出: 1

2 思路

• 1 动态规划

  动态数组dp[i]的定义为以nums[i]为结尾的最长递增子序列长度，那么从头向后遍历，计算dp[i]时，可以对其前边的数进行遍历，当nums[j]<nums[i]时，说明以nums[j]为结尾的递增序列可以在后边直接加上nums[i]构成新的递增序列，也就是说，当满足nums[i]>nums[j]，则有

$$dp[i]= \max \limits_{0\le j < i} (dp[j]+1)$$

  代码如下：

class Solution{
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), ans = 1;
        vector<int> dp(n, 1);
        for(int i = 1; i < n; ++i) {
            for(int j = 0; j < i; ++j)
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j]+1);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

• 2 贪心+二分法

  以上的解法的时间复杂度为$O(n^2)$, 其实可以采用贪心的思路。要获得最长的递增子序列，那么就应该使得当前要加入序列中的元素尽可能的小，从而使得序列递增速度尽可能慢。因而可以创建一个数组tails，其定义为长度为i的递增子序列的末尾元素为tails[i]，与动态规划中动态数组的定义类似。然后遍历整个数组，当nums[i]比当前tails中最后一个元素大时，那么直接将这个元素插到tails中，否则进行二分查找，寻找tails数组中nums[i]应该放的位置，然后将这个位置上的数改为nums[i]。完成遍历后，返回tails的长度即可。

class Solution{
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), len = 1;
        if(n == 0)  return 0;
        vector<int> tails(n+1);
        tails[len] = nums[0];
        for(int i = 1; i < n; ++i) {
            if(nums[i] > tails[len]) {
                tails[++len] = nums[i];
            }else{
                int left = 1, right = len, pos = 0;
                while(left <= right) {
                    int mid = left + (right - left) / 2;
                    if(tails[mid] < nums[i]) {
                        pos = mid;
                        left = mid + 1;
                    }else 
                        right = mid - 1;
                }
                tails[pos+1] = nums[i];
            }
        }
        return len;
    }
}

  另一种写法：

class Solution{
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), res = 0;
        vector<int> tails(n);
        for(int i = 0; i < n; ++i) {
            int left = 0, right = res;
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(tails[mid] < nums[i]) 
                    left = mid + 1;
                else
                    right = mid;
            }
            tails[left] = nums[i];
            if(res == right)    ++res;
        }
        return res;
    }
}

两种写法，前者的效率会稍微高一点，因为后者对于每个新插入的元素都执行了一次二分查找。

二） 面试题 17.08. 马戏团人塔

1 题目描述

• 题目链接：面试题 17.08. 马戏团人塔

有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。

示例1：

输入: height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
输出: 6
解释: 从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)

2 思路

  最直接的思路就是对身高进行排序，然后将对应的体重按身高的顺序调整，然后就转换为最长递增子序列的问题。这题的范围是0-10000，因而采用动态规划的方法将会超时。

  此外，单独对身高或者体重进行排序然后按最长递增子序列求解的话，如果存在身高是有相同，那么求解的结果将会是错误的。因而需要同时对两者进行排序，身高按升序、体重也按升序，当身高一致时体重按降序。然后就是最长递增子序列问题了。

  代码如下：

class Solution {
    static bool cmp(pair<int, int> a, pair<int, int> b) {
        if(a.first == b.first)  return a.second > b.second;
        return a.first < b.first;
    }
public:
    int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
        vector<pair<int, int>> persons;
        int n = height.size();
        for(int i = 0; i < n; ++i)  persons.emplace_back(height[i], weight[i]);
        sort(persons.begin(), persons.end(),cmp);
        int res = 0;
        vector<int> tails(n);
        for(int i = 0; i < n; ++i) {
            int left = 0, right = res;
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(persons[tails[mid]].first<persons[i].first && persons[tails[mid]].second<persons[i].second)
                    left = mid + 1;
                else
                    right = mid;
            }
            tails[left] = i;
            if(right == res)    ++res;
        }
        return res;
    }
};

为什么身高一样的情况下，体重要按降序进行排序呢？这种思路其实就是后插入的元素会将对应位置上先插入的元素进行置换，即保留后插入的元素。如果按升序排序，其实同样身高最后保留的是体重较大的那个，那么就可能存在一种情况，后边有个身高比这个同等身高的高，体重只比这几个身高一样的人中的最轻那个重一点，那么如果保留最重那个，那么这个身高稍微高一点的人就不会保留，而实际上这个应该可能是要保留的，因而如果体重升序则可能导致结果错误。

三） Leetcode 354. 俄罗斯套娃信封问题

1 题目描述

• 题目链接：354. 俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例1：

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例2：

输入: envelopes = [[1,1],[1,1],[1,1]]
输出: 1

2 思路

class Solution {
    static bool cmp(vector<int>& a, vector<int>& b){
        if(a[0] == b[0])    return a[1] > b[1];
        return a[0] < b[0];
    }
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size(), res = 1;
        if(n == 0)  return 0;
        sort(envelopes.begin(), envelopes.end(),cmp);
        vector<int> tails(n+1);
        tails[res] = 0;
        for(int i = 1; i < n; ++i) {
            if(envelopes[i][0]>envelopes[tails[res]][0]&&envelopes[i][1]>envelopes[tails[res]][1]) {
                tails[++res] = i;
            }else{
                int left = 1, right = res, pos = 0;
                while(left <= right) {
                    int mid = left + (right - left) / 2;
                    if(envelopes[tails[mid]][0]<envelopes[i][0] && envelopes[tails[mid]][1]<envelopes[i][1]) {
                        pos = mid;
                        left = mid + 1;
                    }else 
                        right = mid - 1;
                }
                tails[pos+1] = i;
            }
        }
        return res;
    }
};