当前位置：首页 > backend >正文

【华为OD- B卷 - 书籍叠放 200分（python、java、c、c++、js）】

backend 2025/5/21 5:57:07

【华为OD- B卷 - 书籍叠放 200分（python、java、c、c++、js）】

题目

书籍的长、宽都是整数对应 (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]]

输出：

python解法

解题思路：

更新中

java解法

解题思路

解题思路
题目要求：在不允许旋转的前提下，求书籍最多能叠放多少本。
叠放规则：

书A的长和宽都必须大于书B，才能将B放在A之上；

每本书的 (length, width) 都是正整数。

抽象为经典问题：
首先按长度升序排序，若长度相同则按宽度降序排序；

然后在排序后的宽度序列中，求最长严格递减子序列，即可得到最大可叠放数量；

实际上是**俄罗斯套娃信封问题（二维LIS）**的变种；

最终转化为对宽度数组的最长递增子序列（LIS）求解。
使用到的算法
自定义排序将书按长升序，长相同则按宽降序，防止错误嵌套
二维转一维降维处理对排序后的宽度序列做 LIS，转为经典一维问题
LIS + BinarySearch O(n log n) 高效计算最长递增子序列（最优解）

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String input = scanner.nextLine(); // 从控制台读取输入字符串，例如 [[20,16],[15,11],[10,10],[9,10]]int[][] books = parseBooks(input); // 解析输入为二维数组，每本书的长宽System.out.println(findMaxStack(books)); // 输出最多可叠放的书本数量}// 将字符串 "[[20,16],[15,11],...]" 解析为二维 int 数组private static int[][] parseBooks(String input) {// 正则分割出每本书的子串String[] items = input.substring(1, input.length() - 1).split("(?<=]),(?=\\[)");int[][] books = new int[items.length][2];for (int i = 0; i < items.length; i++) {// 去除方括号，提取长宽字符串String[] dimensions = items[i].substring(1, items[i].length() - 1).split(",");books[i][0] = Integer.parseInt(dimensions[0].trim()); // 长度books[i][1] = Integer.parseInt(dimensions[1].trim()); // 宽度}return books;}// 求最多可叠放书籍数private static int findMaxStack(int[][] books) {// 排序规则：按长度升序，长度相同按宽度降序Arrays.sort(books, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);// 将宽度提取为一维数组int[] heights = new int[books.length];for (int i = 0; i < books.length; i++) {heights[i] = books[i][1];}// 对宽度数组求最长递增子序列长度return calculateLIS(heights);}// LIS 最长递增子序列（二分优化，时间复杂度 O(n log n)）private static int calculateLIS(int[] heights) {int[] dp = new int[heights.length]; // dp[i] 表示长度为 i+1 的递增序列的末尾最小值int len = 0; // 当前已构建的最长递增子序列长度for (int height : heights) {// 二分查找 height 应插入的位置int idx = Arrays.binarySearch(dp, 0, len, height);if (idx < 0) idx = -(idx + 1); // 若找不到，得到应插入位置dp[idx] = height; // 更新 dp 数组，尝试更小的末尾if (idx == len) len++; // 扩展 LIS 长度}return len;}
}