题目描述
书籍的长、宽都是整数对应[l, w] (长，宽)。如果书A的长宽度都比B 长宽 大时，则允许将 B 排列放在 A 上面。
现在有一组规格的书籍，书籍叠放时要求书籍不能做旋转
请计算最多能有多少个规格书籍能叠放在一起
输入描述
- 输入：
books = [[20,16],[15,11],[10,10],[9,10]] - 说明：总共有 4 本书籍
- 第一本书的长度为
20宽度为16 - 第二本书的长度为
15宽度为11 - 依次类推
- 最后一本书的长度为
9宽度为10
输出描述
- 输出：3
- 说明：最多 3 个规格的书籍可以叠放到一起，从下到上依次为：
[[20,16],[15,11],[10,10]]
用例
--输入
[[20,16],[15,11],[10,10],[9,10]]
--输出
3题目解析
由题意可知，假设存在A、B两本书，如果B能够叠放在A上面，需要满足 A 的长度和宽度均要大于B的长度和宽度。
存放书籍数据的是一个二维数组，由此可以对二维数组进行排序。 首先根据书本的长度进行排序，书本长度相同的情况下，书本宽度降序排列。如下图
- 通过观察数据可以发现，在保证长度升序排列（当长度相同，根据宽度降序排列）的情况下
- 问题可以转化为求数组的 最长严格递增子序列
- 如上图例子就是问题转化为了求数组
[11, 13, 11, 18, 16]的 最长严格递增子序列
- 那么最长的递增子序列是
[11, 13, 18]
show code
import java.util.Arrays;
import java.util.Objects;
import java.util.Scanner;
/**
* desc : <a href="https://fcqian.blog.csdn.net/article/details/127711745">书籍叠放</a>
* <p>
* create time : 2023/8/19 15:34
*/
public class BookStack {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
String[] split = line.replace("[", "").replace("]", "").split(",");
int n = split.length;
int[][] books = new int[n / 2][2];
int idx = 0;
for (int i = 0; i < n / 2; i++) {
books[i][0] = Integer.parseInt(split[idx++]);
books[i][1] = Integer.parseInt(split[idx++]);
}
//bookStack(books);
}
private static void bookStack(int[][] books) {
// 按照长度进行升序排列，若长度相同则按照宽度降序排列.
Arrays.sort(books, (a, b) -> Objects.equals(a[0], b[0]) ? b[1] - a[1] : a[0] - b[0]);
// 数组已经经过排序，然后这个时候把 第二列数据单独提取出来.
int n = books.length;
int[] widths = new int[n];
for (int i = 0; i < books.length; i++) {
widths[i] = books[i][1];
}
// 然后接下来的问题变成了寻找 最长子序列 长度的问题.
longestLIS(widths);
}
private static void longestLIS(int[] widths) {
int start = 0,n = widths.length;
int[] book = new int[n];
for (int i = 0; i < widths.length; i++) {
// 二分查找当前元素在 book 数组中的位置.
int left = 0,right = start;
// 需要处理当前的数据需要放到 book 数组中的哪一个位置.
int target = widths[i];
while(left < right) {
int mid = (right + left) / 2;
if(book[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
if(left == start) {
start++;
}
book[left] = target;
}
System.out.println(start);
}
}