近期准备校招，在跟牛客网左老师的算法公开课，听他的课受益匪浅，学到了很多解题思想，给我这种小白很大帮助。下面贴出自己根据课程中讲到的思想实现的代码，做个记录，方便自己以后温故。 这篇的内容为最长递增子序列的解法，以及使用其中的一个解题思想来实现一个类似leetcode354. Russian Doll Envelopes的问题。 子序列可以是数组中非连续的元素构成，但是必须在原数组中的相对位置是有一致的先后顺序。
方法一，使用一个辅助数组h[]，h[i]的值表示以原数组中arr[i]结尾最长递增子序列的长度，算法复杂度为O(N*N)
private static int calMaxLength(int []arr) { if (arr == null || arr.length == 0) return 0; int len = arr.length; // 辅助数组，存以arr[i]结尾的最长递增子序列的长度 int h[] = new int[len]; int max = 0; for (int i = 0; i < len; i++) { h[i] = 1; int tmp = h[i]; for (int j = i - 1; j >= 0; j--) { // 当遍历到j时剩下的元素个数不足tmp-1时后面的都可以不考虑了 if (j + 1 < tmp - 1) { break; } if (arr[j] < arr[i]) { if (tmp < h[j] + 1) { tmp = h[j] + 1; } } } h[i] = tmp; max = Math.max(max, h[i]); } System.out.println(Arrays.toString(h)); return max; }方法二，使用一个辅助数组h[]（称为有效数组），长度与原数组一样，h[i]的值表示遍历原数组到当前元素时，长度为i+1的最长递增子序列的最小末尾数是多少。在求h[i]的过程中使用二分法进行加速。算法时间复杂度为O(NlogN)
private static int calMaxLength2(int[] arr) { if (arr == null || arr.length == 0) return 0; int len = arr.length; // 有效值数组 int h[] = new int[len]; h[0] = arr[0]; int maxLen = 0; int max = 1; for (int i = 1; i < len; i++) { int index = binarySearch(h, 0, maxLen, arr[i]); if (index != -1) { //找到，替换 h[index] = arr[i]; } else { //没找到，添加 maxLen++; h[maxLen] = arr[i]; max = maxLen + 1; } } System.out.println(Arrays.toString(h)); return max; } /** * 基于二分查找出arr中第一个大于key的下标 */ private static int binarySearch(int arr[],int fromIndex, int toIndex, int key) { if (toIndex < fromIndex) return -1; int low = fromIndex; int high = toIndex; while (low <= high) { int mid = (low + high) >>> 1; if (arr[mid] < key) { low = mid + 1; } else if (arr[mid] > key) { high = mid - 1; } else { return mid; } } if (low > toIndex) { return -1; } return low; }给定一个 N*2 的二维数组，看作是一个个二元组，例如[[a1,b1],[a2,b2],[a3,b3]]，规定：一个如果想把二元组甲放在二元组乙上，甲中的 a 值必须大于乙中的 a 值，甲中的 b值必须大于乙中的 b 值。如果在二维数组中随意选择二元组，请问二元组最多可以往上摞几个？ 例如：[[5,4],[6,4],[6,7],[2,3]], 最大数量可以摞 3 个，[2,3] => [5,4] => [6,7]：
import java.util.Arrays; import java.util.Scanner; import java.util.Stack; /** * @author hyman * */ public class LongestIncreaseAlignment { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); scanner.nextLine(); int[][] arr = new int[n][2]; for (int i = 0; i < n; i++) { arr[i][0] = scanner.nextInt(); arr[i][1] = scanner.nextInt(); scanner.nextLine(); } scanner.close(); System.out.println(calcMaxLayer(arr)); } /** * O(NlogN)，使用二分查找加速枚举过程 * @param arr * @return */ private static int calMaxLength(int[] arr) { if (arr == null || arr.length == 0) return 0; int len = arr.length; // 有效值数组 int h[] = new int[len]; h[0] = arr[0]; int maxLen = 0; int max = 1; for (int i = 1; i < len; i++) { int index = binarySearch(h, 0, maxLen, arr[i]); if (index != -1) { //找到，替换 h[index] = arr[i]; } else { //没找到，添加 maxLen++; h[maxLen] = arr[i]; max = maxLen + 1; } } System.out.println(Arrays.toString(h)); return max; } /** * 二分查找，找出有序数组arr中第一个大于n的数的下标 * @param arr * @param start 起始位置下标 * @param end 结束位置下标 * @param n * @return */ private static int binarySearch(int arr[],int start, int end, int n) { if (end < start) return -1; if (arr[end] < n) return -1; int mid = (start + end) >>> 1; if (mid == start) { if (arr[mid] >= n) { return mid; } return arr[mid + 1] < n ? -1 : mid + 1; } if (arr[mid] < n) { return binarySearch(arr, mid + 1, end, n); } if (arr[mid] > n) { return binarySearch(arr, start, mid, n); } return mid; } /** * 二维数组，看做是一组二元组，求可以叠的最大层数 * @param arr * @return */ private static int calcMaxLayer(int arr[][]) { if (arr == null || arr.length == 0) return 0; //处理方法：先根据a从小到大排序，a相同则根据b从大到小排序 int n = arr.length; int tmpA = 0, tmpB = 0; for (int i = 0; i < n; i++) { tmpA = arr[i][0]; tmpB = arr[i][1]; for (int j = i - 1; j >= 0; j--) { // 根据a升序排列 if (arr[j][0] > tmpA) { arr[j + 1][0] = arr[j][0]; arr[j + 1][1] = arr[j][1]; if (j == 0) { arr[j][0] = tmpA; arr[j][1] = tmpB; } }else if (arr[j][0] == tmpA) { arr[j + 1][0] = tmpA; //a相等，按b降序列排列 if (arr[j][1] < tmpB) { arr[j + 1][1] = arr[j][1]; // 何时结束 if (j == 0 || arr[j - 1][0] != tmpA) { arr[j][1] = tmpB; } } else { arr[j + 1][1] = tmpB; break; } } else { arr[j + 1][0] = tmpA; arr[j + 1][1] = tmpB; break; } } } //打印排序后的二维数组 for (int i = 0; i < arr.length; i++) { System.out.print("(" + arr[i][0] + ", " + arr[i][1] + ") "); } System.out.println(""); //将二元组中的b存到数组arrB中 int arrB[] = new int[n]; for (int i = 0; i < n; i++) { arrB[i] = arr[i][1]; } return calMaxLength(arrB); } }如果错误，望给予指正，共同学习、共同进步~
