給定一個N*2的二維數組，看作是一個個二元組，[a1,b1],[a2,b2],[a3,b3],規定：如果想把一個二元組甲放到二元組乙上，甲中的a值必須大于乙中的a值，甲中的b值必須大于乙中的b值，如果二維數組中隨意選擇二元組，請問二元組中最多可以往上放多少個？
例如：[[7,8],[5,9],[1,2],[6,4],[8,6]]，則最多可以放三個：[1,2]->[6,4]->[7,8]或[1,2]->[6,4]->[8,6]
要求：實現時間復雜度O(N*logN)的解法


鋪墊：最長遞增子序列求解
例如一個數列：2，1，6，4，5，2，7，4
則其最長遞增子序列有4個：1，4，5，7或2，4，5，7等
O(n2）解法：
生成一個輔助數組h[8],這輔助數組的用于存放必須以第i個數字結尾的子序列長度，即求出以任何一個數字結尾的數列的最長遞增子序列長度。每個數字都要求解以該數字結尾的最長遞增子序列長度，即首先是2，以2結尾的最長遞增子序列就是2，則h[0]=1；之后是1，以1結尾的最長遞增子序列是1，則h[1]=1；之后是6，以6結尾的最長遞增子序列是1，6或者2，6，則h[2]=2,以此類推，則例中的h[8]=[1,1,2,2,3，2，4，3]
O(nlogN)解法：
（ps：看到logN一般就會想到是二分法）
此算法是吧之前的枚舉過程加速
生成一個輔助數組h[8]，首先對于2，直接將2放入,h[0]=2,此時認為之后的h數組都是無效區，只有h[0]是有效區；遇到1時，在有效區中找第一個大于1的數字，利用二分法，因為有效區的有序的，此時由于2>1，則將2換成1，此時h[0]=1，有效區仍然是h[0];
遇到6，在有效區中找第一個大于6的數，但是由于在有效區中沒有找到比6大的數，故此時擴充有效區，此時有效區為[1,6]，則以6結尾的有效區中的長度為2；
之后是4，在有效區中找到第一個大于4的數，故將6換為4，此時有效區為[1,4],則以4結尾的最長遞增子序列是1，4，長度為2；
之后是5，在有效區中擴充，此時有效區為[1,4,5]，以5結尾的最長遞增子序列為1，4，5，長度為3；
之后是2，將4換為2，此時有效區為1，2，5，則以2結尾的最長遞增子序列為1，2，長度為2；
之后是7，擴充有效區，此時以7結尾的最長遞增子序列為1，2，5，7，長度為4；
之后是4，此時，將5換為4，此時最長遞增子序列為1，2，4，7，即以4結尾的最長遞增子序列長度為3。
h[i]的含義是假設當前遍歷到cur，h[i]有效區代表遍歷到cur為止，長度為i+1的最長遞增子序列的最小末尾是什么數，h數組是維持了最小末尾。

public static int[] getdp(int[] arr){int[] dp = new int[arr.length]; //以每個數字結尾的最長遞增子序列的長度int[] ends = new int[arr.length]; ends[0] = arr[0]; int right = 0; //有效區長度int l = 0; //有效區的左邊界int r = 0; //有效區的右邊界int m = 0;for(int i = 1; i<arr.length; i++){l = 0;r = right;while(l<=r){//在有效區中找到最后一個比當前數小的位置m = (1+r)/2;if(arr[i] > ends[m]){l = m + 1;}else{r = m - 1;}}right = Math.max(right, 1);//若沒有找到，擴充有效區ends[i] = arr[i];dp[i] = 1 + i;//以當前數結尾的最長遞增子序列長度}return dp; }



以下求解原題：
一種解法是時間復雜度為O（n2），先按照a升序排序，如果a相等時，以b升序排序，得到一個序列，之后在此序列中對b查找最長遞增子序列。
本題時間復雜度為O(nLogN)排序策略是，先按照a的值升序排序，當a相等時，以b降序排序。
生成一個輔助數組h[],此時h中放入的是b的值。在a相等時，只關注b，更新h，h只維持b出現的最小末尾。

import java.util.Arrays; import java.util.Comparator;public class RussianDollEnvelopes{public static class Dot{public int w;public int h;public Dot(int weight, int high){w = weight;h = high;}}public static class DotComparator implements Comparator<Dot>{//定義Dot比較器,若返回-1，則arg0放在前面，若返回1，表示arg1放在前面@Overridepublic int compare(Dot arg0, Dot arg1){if(arg0.w == arg1.w){if（arg0.h == arg1.h）{return 0;}else if(arg0.h < arg1.h){return 1;}else{return -1;}}else if(arg0.w < arg1.w){return -1;}else{return 1;}}}public static int maxEnvelopes(int[][] es){if(es == null || es.length == 0 || es[0] == null || es[0],length != 2){return 0;}}Dot[] dots = new Dot[es.length];for(int i =0; i<es.length;i++){dots[i] = new Dot(es[i][0], es[i][1]);}Arrays.sort(dots, new DotComparator());//調用排序方法int[] ends = new int[es.length];ends[0] = dots[0].h;int right = 0;int l = 0;int r = 0;int m = 0;for(int i = 1; i<dots.length;i++){l = 0;r = right;while(l <= r){m = (1+r)/2;if(dots[i].h >ends[m]){l = m + 1;}else{r = m - 1;}}right = Math.max(right, l);ends[1] = dots[1].h;}return right+1; }public static void main(String[] args){//... }

總結

以上是生活随笔為你收集整理的俄国沙皇问题笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。