华为OD机试 - 书籍叠放 - 逻辑分析（Java 2023 B卷 200分）

题目描述

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

解题思路

这个问题可以转化为一个最长递增子序列（LIS）的问题。我们需要找到一组书籍，使得每本书的长度和宽度都比前一本小。为了简化问题，我们可以先对书籍进行排序，然后使用动态规划来找到最长的序列。

代码实现

Java

import java.util.Arrays;
import java.util.Comparator;

public class MaxBooks {
    public int maxBooks(int[][] books) {
        // 按长度降序排序，如果长度相同则按宽度降序排序
        Arrays.sort(books, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) {
                    return b[1] - a[1];
                } else {
                    return b[0] - a[0];
                }
            }
        });

        int[] dp = new int[books.length];
        int len = 0;
        for (int[] book : books) {
            int i = Arrays.binarySearch(dp, 0, len, book[1]);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = book[1];
            if (i == len) {
                len++;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        MaxBooks solution = new MaxBooks();
        int[][] books = {{20, 16}, {15, 11}, {10, 10}, {9, 10}};
        System.out.println(solution.maxBooks(books)); // 3
    }
}

Python

import bisect

class Solution:
    def maxBooks(self, books):
        # 按长度降序排序，如果长度相同则按宽度降序排序
        books.sort(key=lambda x: (-x[0], -x[1]))
        
        dp = []
        for book in books:
            idx = bisect.bisect_left(dp, book[1])
            if idx == len(dp):
                dp.append(book[1])
            else:
                dp[idx] = book[1]
        return len(dp)

solution = Solution()
books = [[20, 16], [15, 11], [10, 10], [9, 10]]
print(solution.maxBooks(books))  # 3

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxBooks(vector<vector<int>>& books) {
        // 按长度降序排序，如果长度相同则按宽度降序排序
        sort(books.begin(), books.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0]) {
                return a[1] > b[1];
            } else {
                return a[0] > b[0];
            }
        });

        vector<int> dp;
        for (const auto& book : books) {
            auto it = lower_bound(dp.begin(), dp.end(), book[1]);
            if (it == dp.end()) {
                dp.push_back(book[1]);
            } else {
                *it = book[1];
            }
        }
        return dp.size();
    }
};

int main() {
    Solution solution;
    vector<vector<int>> books = {{20, 16}, {15, 11}, {10, 10}, {9, 10}};
    cout << solution.maxBooks(books) << endl; // 3
    return 0;
}

JavaScript

var maxBooks = function(books) {
    // 按长度降序排序，如果长度相同则按宽度降序排序
    books.sort((a, b) => {
        if (a[0] === b[0]) {
            return b[1] - a[1];
        } else {
            return b[0] - a[0];
        }
    });

    let dp = [];
    for (let book of books) {
        let left = 0, right = dp.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (dp[mid] < book[1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (left === dp.length) {
            dp.push(book[1]);
        } else {
            dp[left] = book[1];
        }
    }
    return dp.length;
};

let books = [[20, 16], [15, 11], [10, 10], [9, 10]];
console.log(maxBooks(books)); // 3

复杂度分析

• 时间复杂度: O(n log n)，其中n是书籍的数量。排序的时间复杂度是O(n log n)，而动态规划部分的时间复杂度也是O(n log n)。
• 空间复杂度: O(n)，用于存储动态规划数组。

总结

我们使用了排序和动态规划来解决这个问题。首先对书籍进行排序，然后使用二分查找来优化动态规划的过程。这种方法能够有效地找到最长的书籍叠放序列。