搭积木

先排序，然后利用二分查找求长所组成的数组的最长非递减子列的长度，O(NlgN)

import java.util.*;
public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int N = sc.nextInt();
         Block[] arr = new Block[N];
         for (int i = 0; i < N; i++) {
             arr[i] = new Block(sc.nextInt(), sc.nextInt());
         }

         Arrays.sort(arr, new Comparator() {
             public int compare(Block b1, Block b2) {
                 return b1.W != b2.W ? b1.W - b2.W : b1.L - b2.L;
             }
         });

         int[] spera = new int[N];
         spera[0] = arr[0].L;
         int right = 0;
         int l = 0;
         int r = 0;
         int mid = 0;
         for (int i = 1; i < N; i++) {
             l=0;
             r=right;
             while (l <= r) {
                 mid = l + (r - l) / 2;
                 if (arr[i].L >= spera[mid]) {
                     l = mid + 1;
                 } else {
                     r = mid - 1;
                 }
             }
             right = Math.max(right, l);
             spera[l] = arr[i].L;
         }
        System.out.println(right + 1);
    }
}

class Block {
     public int W;
     public int L;
     public Block(int W,int L){
         this.W=W;
         this.L=L;
    }
}

// O(nlogn), O(n)
let num = readline()
num = parseInt(num)
let arr = []
while(line = readline()) {
    let [w, l] = line.split(' ')
    arr.push([parseInt(w), parseInt(l)])
}


// 1. sort by width increasing order
arr.sort((a,b) => {
    if (a[0] === b[0]) {
        return a[1] - b[1] // must do this also
    } else {
        return a[0] - b[0]
    }
})

// 2. find length of longest increasing subsequence (not continuous)
let nums = arr.map(i => i[1]) // get lengths
const lengthOfLIS = function(nums) {
    if (nums === null || nums.length === 0) return 0;
    if (nums.length === 1) return 1;
    let len = 0; // final ans
    
    let dp = new Array(nums.length).fill(0);
    for (let i = 0; i < nums.length; i++){
        let pos = binarySearchPosition(dp, nums[i], 0, len);
        dp[pos] = nums[i];
        if (pos === len) len++;
    }

    return len;
};

const binarySearchPosition = (dp, target, start, end) => {
    while (start < end) {
        let mid = Math.floor((start + end)/2);
        if (target >= dp[mid]) start = mid+1;
        else end = mid;
    }
    return end;
}

// print
print(lengthOfLIS(nums))

#include<iostream>
(720)#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1000005;
struct NODE
{
    int w;
    int l;
    int id;
}node[maxn];
int f[maxn];
int N;
int lowbit(int x)
{
    return x&(-x);
}

void add(int index, int val)
{
    for (int i = index; i <= N; i += lowbit(i))
    {
        f[i] = max(f[i], val);
    }
}

int query(int index)
{
    int res = 0;
    for (int i = index; i > 0; i -= lowbit(i))
    {
        res = max(res, f[i]);
    }
    return res;
}
bool cmp(const NODE& a, const NODE& b)
{
    if (a.w != b.w) return a.w < b.w;
    else return a.l < b.l;
}
int main()
{

    while (cin>> N)
    {
        for (int i = 1; i <= N; i++)
        {
            cin>> node[i].w>> node[i].l;
            node[i].id = i;
        }
        if (N == 1)
        {
            cout<< 1<< endl;
            continue;
        }
        sort(node+1, node+N+1, cmp);
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= N; i++)
        {
            add(node[i].id, query(node[i].id)+1);
        }
        cout<< query(N)<< endl;
    }
    return 0;
}

先对宽排序。

那么问题就转化成：寻找此时所有长的最长不递减子序列。（注意：与上升还是有点区别）

因为数据量 N 的限制是一百万，所以需要使用 LIS 问题 O(nlogn) 的解法，而不能使用O(n^2)的动态规划解法，会TLE。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for(int i = 0; i < n; i ++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        // 因为 W 都是正数，所以直接做差排序是没问题的。
        Arrays.sort(arr, (e1, e2) -> e1[0] - e2[0]);

        int[] top = new int[n];
        int piles = 0;
        for(int i = 0; i < n; i ++) {
            int target = arr[i][1];

            int l = 0;
            int r = piles;
            while(l < r) {
                int mid = (l + r) >>> 1;
                if(top[mid] > target) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }

            if(l == piles) piles ++;
            top[l] = target;
        }

        System.out.println(piles);
    }
}

这个方法运行超时：感觉还可以抢救一下：
import java.awt.Point;
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
Point[] array =new Point [n];
int [] array1=new int [n];
for (int i = 0; i < n; i++)
array[i]= new Point(sc.nextInt(),sc.nextInt());
Arrays.sort(array, new Comparator<Point>() {
@Override public int compare(Point p1, Point p2) {
if( p1.x == p2.x )
return p1.y-p2.y;
return p1.x-p2.x;
}
});
array1[0]=0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if(array[i].y<=array[j].y)
array1[j]=Math.max(array1[i]+1,array1[j]);
for (int i = 1; i < n; i++)
array1[i]=Math.max(array1[i-1], array1[i]);
System.out.println(array1[n-1]+1);
}
}

//对二楼的代码进行了一些精简，占用空间会更小一些，主要是数组a使用一维的就可以了，以及数字输入过程中不需要中间变量P
//顺便加了点注释方便阅读
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cmp (pair<int, int>a, pair<int, int>b);
int main(){
    //输入数据存入pair,第一个元素为积木宽W，第二个元素为积木长L
    long long a[1000001];
    long long dp[1000001];
    int i,j;
    int n;
    cin>>n;
    int k1,k2;
    vector<pair<int,int> > vec;
    for(i=0;i<n;i++){
        cin>>k1;
        cin>>k2;
        vec.push_back({k1,k2});
    }
    
    //与cmp函数配合实现以pair的第一个元素顺序升序排列
    sort(vec.begin(), vec.end(), cmp);
    for(i=0;i<vec.size();i++){
        a[i]=vec[i].second;
    }
    
    //二分+dp求最长上升子序列
    dp[1]=a[0];
    int len=1;
    for(int i=1;i<n;i++)
    {
        if(a[i]>=dp[len])
            dp[++len]=a[i];
        else
        {
            int j=lower_bound(dp,dp+len,a[i])-dp;
            dp[j]=a[i];
        }
    }
    cout<<len<<endl;
    return 0;
}

//升序排列
int cmp(pair<int, int>a, pair<int, int>b)
{
    return a.first<b.first;
}

public static void main(String[] args) {  Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Point[] ps = new Point[N];  //这里x是宽，y是长
        for (int i = 0; i  ps[i] = new Point(sc.nextInt(),sc.nextInt());  }
        Arrays.sort(ps, new Comparator() {  @Override  public int compare(Point p1, Point p2) {  //对x（宽）排序  if( p1.x == p2.x )  return p1.y-p2.y;  return p1.x-p2.x;  }  });
        TreeSet dpSet = new TreeSet(new Comparator() {  //与上面不同，这里x是长，y是最大层数，该数据为特定长对应的最大长度  @Override  public int compare(Point o1, Point o2) {  return o1.x - o2.x;  }  }) ;
        for (Point p : ps) {  Point dp = new Point(p.y, 1);  Point dpTmp = dpSet.floor(dp);  //获取长小于等于p的数据  if( dpTmp == null ){  //数据不存在，此时的长最小，最大层数为1  dpSet.add(dp);  }else{  if( dpTmp.x == p.y ){  //若恰有该长的数据，数据对象最大层数+1  dp = dpTmp;  dp.y ++;  }else{  //若无对应数据，将新增点的层数设为小于其的点的层数+1  dp.y = dpTmp.y + 1;  dpSet.add(dp);  }  }  if( (dpTmp = dpSet.higher(dp)) != null && dpTmp.y == dp.y )  dpSet.remove(dpTmp);  //清理其后等于其层数的元素，因为若有后来的方块，只会叠加到此方块下，而不会选择长更大的方块  }
        System.out.println(dpSet.last().y);  }

import java.util.*;

/*
俄罗斯套娃信封问题
首先将积木按照宽度升序排列
比如针对信封[[3,2],[2, 4],[4,3],[5, 6],[6,5]排序后变为
w: 2 -> 3 -> 4 -> 5 -> 6
h: 4 -> 2 -> 3 -> 6 -> 5
问题转化为：
求长度数组h的最长升序子序列的长度
*/
public class Main {
    public static void main(String[] args) {
        // 获取输入
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        if (N == 0) {
            System.out.println(0);
            return;
        }
        int[][] matrix = new int[N][2];
        for (int i = 0; i < N; ++i) {
            matrix[i][0] = scanner.nextInt();
            matrix[i][1] = scanner.nextInt();
        }

        // 按照宽度排序，宽度一样按长度排序
        Arrays.sort(matrix, (int[] r1, int[] r2)->{
            if (r1[0] == r2[0]) {
                return r1[1] - r2[1];
            } else {
                return r1[0] - r2[0];
            }
        });

        // 求长度数组的最长升序子序列的长度
        List<Integer> subOrder = new ArrayList<>();
        // 先将第0个矩形的长度放入
        subOrder.add(matrix[0][1]);

        // 从第1个开始向后遍历
        for (int i = 1; i < N; ++i) {
            // 若大于等于序列的最后一个，添加在序列尾
            if (matrix[i][1] >= subOrder.get(subOrder.size() - 1)) {
                subOrder.add(matrix[i][1]);
            } else {
                // 否则，在序列中找到此值的插入位置,由于序列是有序的，使用二分查找
                int index = Collections.binarySearch(subOrder, matrix[i][1]);
                if (index >= 0) {
                    // 若找到相等的则跳过
                    continue;
                } else {
                    // 否则将该位置的数替换为此数
                    index = - index - 1;
                    subOrder.set(index, matrix[i][1]);
                }
            }
        }

        System.out.println(subOrder.size());
    }
}

import java.util.*;
public class Main{
        public static void main(String[] args){
            Scanner input = new Scanner(System.in);
            int N = input.nextInt();
            int[][] a = new int[N][2];
            for (int i = 0;i<N;i++){
                for (int j =0 ;j<2;j++){
                    a[i][j] = input.nextInt();
                }
            }

            //排序：升序,按第一位的升序排列，为了后面只用比较第二列数据做准备
            Arrays.sort(a, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if(o1[0]==o2[0])return o1[1]-o2[1];
                    return o1[0]-o2[0];
                }
            });

            //寻找最高的积木层数
            int count = 1;//起始层数为1
            int max = a[0][1];//中间数
            for(int i = 1;i<N;i++){
                if(max<=a[i][1]){
                    max = a[i][1];
                    count++;
                }
            }
            System.out.println(count);
            input.close();
   }
}

/*
对长方形的宽w排序，本题化简为对长l求最长上升子序列。
本题只需求最长上升子序列的 长度，可优化到O(nlogn)
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1000000
 
struct rectangle {
    int w = 0, l = 0;
} a[N];
int dp[N];
 
bool cmp(rectangle x, rectangle y){
    return x.w == y.w ? x.l < y.l : x.w < y.w;
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i].w >> a[i].l;
    }
    sort(a, a + n, cmp);
    dp[0] = a[0].l;
    int len = 1;
    for(int i = 1; i < n; i++) {
        if(a[i].l >= dp[len-1]) {
            dp[len++] = a[i].l;
        } else {
            *(upper_bound(dp, dp + len, a[i].l)) = a[i].l;
        }
    }
    cout << len << endl;
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.TreeSet;

public class Solution3_搭积木 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        //保存积木的宽高的二维数组
        int[][] bricks = new int[n][2];
        String[] strs;
        for (int i = 0; i < n; i++) {
            strs = bf.readLine().split(" ");
            bricks[i][0] = Integer.parseInt(strs[0]);
            bricks[i][1] = Integer.parseInt(strs[1]);
        }
        if (n==1){
            System.out.println(1);
            return;
        }
        //按照宽进行排序,然后求长度的最长上升子序列
        Arrays.sort(bricks, (a, b) -> a[0] - b[0]);
        /**
         * 我们按照宽度从小到大对 bricks 进行了排序
         * dp数组中存储的数积木的长度，它是一个上升的数组，这样才能保证积木的层叠
         */
        int[] dp = new int[n];
        int count = 0;//层数
        for (int i = 0; i < n; i++) {
            if (count == 0 || bricks[i][1] >= dp[count - 1]) {
                //当当前积木的长度 >= dp数组中保存的最大积木长度，那我们就将它加入到 dp 数组中,并且层数加一
                dp[count] = bricks[i][1];
                count++;
            }else {
                /**
                 * 这里解释一下：当我们加入的积木 bricks[i][1],它的长度小于dp中的最大长度
                 * 我们需要在数组dp中找到 <= bricks[i][1] 最接近的值的索引 index，将它替换成现在的长度 bricks[i][1]
                 * 为什么要替换: dp数组中积木的宽度都是小于 bricks[i]的，积木bricks[i]的宽度比dp[index]宽度大，
                 * 而且bricks[i]的长度 >= dp[index],在堆积木情况下，当然是优先选择宽度和长度更大的积木。
                 */
                int index = lowerBound(dp, 0, count, bricks[i][1]);
                dp[index] = bricks[i][1];
            }
        }
        System.out.println(count);
    }
    /**
     * C++中存在的两个方法，用java实现一下
     * ower_bound算法要求在已经按照非递减顺序排序的数组中找到第一个大于等于给定值key的那个数的索引，
     * 其基本实现原理是二分查找
     */
    public static int lowerBound(int[] nums,int l,int r,int target){
        while(l<r){
            int m = (l+r)/2;
            if(nums[m]>=target) r= m;
            else    l = m +1;
        }
        return l;
    }

    /**
     * upper_bound函数要求在按照非递减顺序排好序的数组中找到第一个大于给定值key的那个数索引，
     * 其基本实现原理是二分查找
     */
    public static int upperBound(int []nums ,int l,int r, int target){
        while(l<r){
            int m = (l+r)/2;
            if(nums[m]<=target) l = m+1;
            else    r = m;
        }
        return l;
    }
}

/*
哪位大佬帮看一下啊？小数据测试都没问题，当积木数量到了10000之后，就报错了。找了很久不知道哪里出问题了 Q^Q

• public class DaJiMu {

  public static void main(String[] args) throws IOException {

    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    int num = Integer.parseInt(bufferedReader.readLine());
    int[][] jimu = new int[num][2];
    for (int i = 0; i < num; i++){
        String[] temp = bufferedReader.readLine().split(" ");
        jimu[i][0] = Integer.parseInt(temp[0]);
        jimu[i][1] = Integer.parseInt(temp[1]);
    }
    Arrays.sort(jimu, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {
            return o1[0] != o2[0]? o1[0] - o2[0] : o1[1] - o2[1];
        }
    });
    if( num == 1){
        System.out.print(1);
        return;
    }
    int max = 0;
    int[] len = new int[num];
    len[0] = 1;
    //求最长递归子序列
    for (int i = 1; i < num; i++){
        int lastADDIndex = binarySearch(jimu, jimu[i][1], 0, i - 1);
        //若非递减，则选择max(len[i-1]+1, len[差值最小]+1)较大的长度。
        if (jimu[i][1] >= jimu[i-1][1])
            if(lastADDIndex != -1)
                len[i] = Math.max(len[i-1] + 1, len[lastADDIndex] + 1);
            else
                len[i] = len[i-1] + 1;
        else{
            if(lastADDIndex != -1){
                len[i] = len[lastADDIndex] + 1;
            }else
                len[i] = 1;
        }
        if( max < len[i])
            max = len[i];
    }
    System.out.print(max);

  }

  public static int binarySearch(int[][] arr, int key, int start, int end){

    int max = -1;
    int min = 1000000000;
    while(start <= end){
        int mid = start + (end - start) / 2;
        if(arr[mid][1] <= key) {
            if(min > key - arr[mid][1]) {
                min = key - arr[mid][1];
                max = mid;
            }
            start = mid + 1;
        }
        else
            end = mid - 1;
    }
    return max;

  }
  }

import bisect
while True:
    try:
        n = int(input())
        jimu_list = []
        for _ in range(n):
            l, w = map(int, input().split())
            jimu_list.append((l, w))
        # 先按照长 由小到大排序 在此基础上只需要判断宽的最长递增子序列即可
        jimu = list(sorted(jimu_list, key=lambda x: x[0]))
        a = []
        for jimu_info in jimu:
            index = bisect.bisect_right(a, jimu_info[1])
            if index == len(a):
                a.append(jimu_info[1])
            else:
                a[index] = jimu_info[1]
        print(len(a))
        
    except:
        break

这份代码报内存超限，请问一下大家有解决的方法吗？还是说python写二分查找这种，就只能内存超限，谢谢大家~

import sys

def solution(num, inputs):
    if num == 0:
        return 0
    inputs = sorted(inputs, key=lambda x:x[0])
    
    dp = [0 for _ in range(num)]
    dp_len = 1
    dp[0] = inputs[0][1]
    for i in range(1, num):
        if inputs[i][1] >= dp[dp_len-1]: 
            dp[dp_len] = inputs[i][1]
            dp_len += 1
        else:    
            index = binarySearch(dp, dp_len, inputs[i][1])
            print(index)
            dp[index] = inputs[i][1]
    return dp_len
    

# 数组中第一个大于或等于key的值
def binarySearch(nums, nums_len, key): 
    l = 0
    h = nums_len - 1
    
    while l <= h:
        mid = l + (h-l) // 2
        if key == nums[mid]:
            return mid
        elif key < nums[mid]:
            h = mid - 1
        else:
            l = mid + 1
    
    return l

n = int(sys.stdin.readline().strip())
li = []
for i in range(n):
    line = sys.stdin.readline().strip()
    lines = list(map(int, line.split()))
    li.append(lines)

print(solution(n, li))

#include <cstdio>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

bool cmp(const pair<int,int>& p1, const pair<int,int>& p2) 
{
    if (p1.first == p2.first)
        return p1.second < p2.second;
    return p1.first < p2.first;
}

int main()
{
    int n;
    scanf("%d", &n);
    vector<pair<int,int>> pairs(n);
    vector<int> d(n+1, INT_MAX);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &pairs[i].first, &pairs[i].second);
    sort(pairs.begin(), pairs.end(), cmp);
    int p = 0;
    for (int i = 0; i < n; ++i)
    {
        int left = 1, right = p;
        while (left <= right)
        {
            int mid = left+(right-left)/2;
            if (d[mid] <= pairs[i].second)
                left = mid+1;
            else 
                right = mid-1;
        }
        d[left] = pairs[i].second;
        if (left > p) p++;
    }
    printf("%d\n", p);
    
    return 0;
}

// dp复杂度有点大，通不过   写一个好理解的二分
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
struct Node{
    int L;
    int W;
    Node(){}
    Node(int _L, int _W) :L(_L), W(_W){}
};



class Solution {
    public:
     static bool cmp(const Node node1,const Node node2){
         return node1.W == node2.W? node1.L < node2.L : node1.W < node2.W;
     }
     // dp时间复杂度太大
     /*
     int getMax(vector<Node> &arr){
         sort(arr.begin(),arr.end(),cmp);
         vector<int> dp(arr.size(),0);
         int maxdp = 0;
         for(int i=0;i<arr.size();i++){
             dp[i] = 1;
             for(int j=0;j<i;j++){
                 if(arr[j].L <= arr[i].L){
                     dp[i] = max(dp[i],dp[j] + 1);
                 }
             }
             maxdp = max(maxdp,dp[i]);
         }
         return maxdp;
     }
     */
    //为啥别人写的二分好难懂，弄一个好懂的
    int getMax2(vector<Node> &arr){
        sort(arr.begin(),arr.end(),cmp);
        vector<int> lsNum;
        for(int i=0;i<arr.size();i++){
            if(lsNum.size() == 0 || lsNum[lsNum.size()-1] <= arr[i].L){
                lsNum.push_back(arr[i].L);
                continue;
            }
            int low = 0;
            int high = lsNum.size()-1;
            while(low < high){
                int mid = low + (high-low)/2;
                if(lsNum[mid] > arr[i].L){
                    high = mid ;
                }else{
                    low = mid + 1;
                }
            }
            lsNum[low] = arr[i].L;
            
        }
        return lsNum.size();
        
    }
};

int main(){
    int N;
    cin>>N;
    vector<Node> arr;
    int l,w;
    for(int i=0;i<N;i++){
        cin>>l>>w;
        arr.push_back(Node(l,w));
    }
    Solution c1;
    cout<<c1.getMax2(arr)<<endl;
    return 0; 
}