信封嵌套问题

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    static bool cmp(vector<int>& a, vector<int>& b)
    {
        return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        if(letters.empty())
            return 0;
        int n = letters.size();
        // 这一步是将二维转为一维问题
        sort(letters.begin(), letters.end(), cmp);
        // 下面的这个是求解 最长递增子数组
        vector<int> f(n, 1);
        for(int i=1; i<n; i++)
        {
            for(int j=0; j<i; j++)
            {
                if(letters[j][1] < letters[i][1])
                    f[i] = max(f[i], f[j] + 1);
            }
        }
        return *max_element(f.begin(), f.end());
    }
};

package main

import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param letters int二维数组 
 * @return int
*/
func maxLetters( letters [][]int ) int {
    n:=len(letters)
    sort.Slice(letters,func(i,j int)bool{
        return letters[i][0]<letters[j][0]
    })
    ans:=1
    dp:=make([]int,n)
    for i,lt:=range letters{
        dp[i]=1
        for j:=0;j<i;j++{
            if lt[0]>letters[j][0]&&lt[1]>letters[j][1]{
                dp[i]=max(dp[i],dp[j]+1)
            }
        }
        if ans<dp[i]{
            ans=dp[i]
        }
    }
    return ans
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    public int maxLetters (int[][] letters) {
        // write code here
        Arrays.sort(letters, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]!=o2[0]){
                    return o1[0]-o2[0];
                }else{
                    return o2[1]-o1[1];
                }
            }
        });
        List<Integer> hs = new ArrayList<>();
        for(int i=0;i<letters.length;i++){
            int tmp = letters[i][1];
            if(hs.isEmpty()||hs.get(hs.size()-1)<tmp){
                hs.add(tmp);
            }else{
                int l = 0;
                int r = hs.size()-1;
                while(l<=r){
                    int mid = (l+r)/2;
                    if(hs.get(mid)<tmp){
                        l = mid+1;
                    }else{
                        if(mid==0||hs.get(mid-1)<tmp){
                            hs.set(mid,tmp);
                            break;
                        }else{
                            r = mid-1;
                        }
                    }
                }
            }
        }
        return hs.size();
    }
}

暴力递归

class Solution {
public:
    static bool cmp (const vector<int> a,const vector<int> b)
    {
        if(a[0]!=b[0])
            return a[0]<b[0];
        else
            return a[1]<b[1];
    }
    int process(vector<vector<int> >& letters, int len,int wide,int times,int index)
    {
        if(index==letters.size())
            return times;

        if(len>=letters[index][0] || wide>=letters[index][1])
            return process(letters,len,wide,times,index+1);
        // 要当前的信封
        int letterin=process(letters,max(len,letters[index][0]),max(wide,letters[index][1]),times+1,index+1);
        // 不要当前的信封
        int letterout=process(letters,len,wide,times,index+1);
        return max(letterin,letterout);
    }
    int maxLetters(vector<vector<int> >& letters) {
        // 首先对 lectters 排序
        sort(letters.begin(),letters.end(),cmp);
        int count = process(letters,0,0,0,0);
        return count;
    }
};

import java.util.*;

class Envelope {
    public int len;
    public int wid;
    public Envelope(int weight, int height) {
        this.len = weight;
        this.wid = height;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    public int maxLetters (int[][] letters) {
        // write code here
        if (letters.length == 0 || letters[0].length == 0)
            return 0;
        Envelope[] env = getSortedEnvelopes(letters);
        int[] arr = new int[env.length];
        for (int i = 0; i < env.length; i++) {
            arr[i] = env[i].wid;
        }
        return getLongestSeq(arr);
    }
    
    //找arr中最长递增子序列
    public int getLongestSeq(int[] arr) {
        int[] dp = new int[arr.length];
        int[] ends = new int[arr.length];
        int right = 0;
        int l = 0;
        int mid = 0;
        int r = 0;
        dp[0] = 1;
        ends[0] = arr[0];
        int max = dp[0];
        for (int i = 0; i < arr.length; i++) {
            l = 0;
            r = right;
            while (l <= r) {
                mid = (l+r) / 2;
                if (arr[i] > ends[mid])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            if (r == right)
                right++;
            ends[l] = arr[i];
            dp[i] = l+1;
            max = Math.max(max, dp[i]);
        }
        return max;
    }
    
    
    public class EnvelopeComparator implements Comparator<Envelope> {
        @Override
        public int compare(Envelope o1, Envelope o2) {
            //为了避免长度相同的情况下，宽度小的被宽度大的误认为可以嵌套
            //换句话说，按这个排列，但看宽度数组，如是你想宽度比我小，除非你长度比我小
            //否则长度若一样，前面的宽度肯定比后面的宽度大
            return o1.len != o2.len ? o1.len - o2.len : o2.wid - o1.wid;
        }
    }
    
    public Envelope[] getSortedEnvelopes (int[][] matrix) {
        Envelope[] res = new Envelope[matrix.length];
        for (int i = 0; i < matrix.length; i++) {
            res[i] = new Envelope(matrix[i][0], matrix[i][1]);
        }
        Arrays.sort(res, new EnvelopeComparator());
        return res;
    }
}

class Solution {
    public:
    
    static bool cmp(vector<int>&a,vector<int>&b){
        if(a[0]!=b[0]) return a[0]<b[0];
        else return a[1]>b[1];
    }

    int maxLetters(vector<vector<int> >& letters) {
        /*
            letters的第一列理解为长度 第二列理解为宽度
            先按长度升序 当长度相同时宽度降序
            便于后边求解LIS
        */
        sort(letters.begin(), letters.end(), cmp); 
        vector<int> b; //存取宽度数据 
        for (int i = 0; i < letters.size(); i++) {
            b.push_back(letters[i][1]);
        }

        //贪心+二分求解最长递增子序列长度
        vector<int> res; //遍历宽度的过程中的贪心LIS
        res.push_back(b[0]); //第一个宽度总可以无条件放进来
        int maxl = 0; //遍历中更新的LIS长度
        for(int i = 1; i < b.size(); i++) {
            if (b[i] > res.back()) {
                res.push_back(b[i]);
            }else {
                int pos = lower_bound(res.begin(), res.end(), b[i]) - res.begin(); //二分
                res[pos] = b[i];
            }
        }
        maxl = res.size(); //最后贪心res长度就是LIS的长度 贪心 总是局部最优嘛
        return maxl;
    }
};

class Solution:
    def maxLetters(self , letters ):
        # write code here
        # 其实第一个肯定能套进去。
        result = 1
        pre = 0
        letters = sorted(letters, key = lambda x:(x[0],x[1]))
        for i in range(1, len(letters)):
            if letters[i][0] > letters[pre][0] and letters[i][1] > letters[pre][1]:
                result += 1
                pre = i
        return result

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    int res3 = 0;
    int cur = 0;
    public int maxLetters (int[][] letters) {
        // write code here
        int[] dp = new int[letters.length];
        for (int i = 0; i < letters.length; i++) {
            dfs(letters, dp,  i , letters[i][0], letters[i][1], 1, true);
            dp[i] = cur;
        }
        return res3;
    }

    public void dfs(int[][] letters, int[] dp, int cur, int length, int width,  int size, boolean flag) {
        for (int i = 0; i < letters.length; i++) {
            if (letters[i][0] < length && letters[i][1] < width){
                if (dp[i] != 0) {
                    size += dp[i];
                    break;
                }
                flag = false;
                dfs(letters, dp, i, letters[i][0], letters[i][1], size + 1, true);
            }
        }
        if (flag) {res3 = Math.max(res3, size); cur = size;}
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param letters int二维数组 
# @return int
#
class Solution:
    def maxLetters(self , letters ):
        letters.sort(key=lambda x: (x[0], -x[1]))
        w, h = 0, 0
        cnt = 0
        # 转换成最长递增子序列的问题了
        def bs(nums, target):
            # 找到第一个比target大的数，返回index
            l, r = 0, len(nums)-1
            while l < r:
                m = l + ((r-l)>>1)
                if nums[m] >= target:
                    r = m
                else:
                    l = m + 1
            return l if nums[l] >= target else l+1
        l = []
        for i in range(len(letters)):
            if not l&nbs***bsp;l[-1] < letters[i][1]:
                l.append(letters[i][1])
            else:
                idx = bs(l, letters[i][1])
                l[idx] = letters[i][1]
        return len(l)

动态规划+二分查找
时间复杂度O(nlogn)
空间复杂度O(n)
1.将数组按照从小到大排序；
2.维护两个数组f,g;f[i]表示第i个信封能够嵌套的层数，g[i]表示嵌套层数为i的信封中最后一个信封宽度的最小值；g是单调递增的序列；
3.从前往后遍历数组，保证g数组中信封的长度小于当前信封；利用二分从g数组中查找宽度小于当前数组的最后一个嵌套信封，记其层数为x，当前信封能够嵌套的最大层数就是x+1。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& w) {
        // write code here
        sort(w.begin(), w.end());
        int n = w.size();
        vector<int> f(n, 0), g(1, 0);
        int ans = 0;
        for (int i = 0, j = 0; i < n; i ++) {
            while (w[j][0] != w[i][0]) {
                if (g.size() == f[j]) g.push_back(w[j][1]);
                else g[f[j]] = min(g[f[j]], w[j][1]);
                j ++;
            }
            int l = 0, r = g.size() - 1;
            while (l < r) {
                int m = l + r + 1 >> 1;
                if (w[i][1] > g[m]) l = m;
                else r = m - 1;
            }
            f[i] = r + 1;
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

function maxLetters( letters ) {
    // write code here
    let  len = letters.length
    if(!len) return 0
    letters.sort((a,b)=> a[0]=== b[0]? a[1]-b[1]:a[0]-b[0])
    const dp = new Array(len).fill(1)
    dp[0] = 1
    for(let i = 1;i<len;i++){
        for(let j = 0;j<i;j++){
            if(letters[i][1]>letters[j][1] && letters[i][0] !== letters[j][0]){
                dp[i] = Math.max(dp[i], dp[j]+1)
            }
    }
}
    return Math.max(...dp)
}