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

最新推荐文章于 2025-05-20 22:23:34 发布

CodeClimb

最新推荐文章于 2025-05-20 22:23:34 发布

阅读量277

点赞数 3

文章标签： java 华为od python c++ c语言

本文链接：https://blog.csdn.net/CodeClimb/article/details/148097815

版权

【华为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;
    }
}