刷题笔记合集🔗

书籍叠放

问题描述

书籍的长、宽都是整数对应 。如果书 A 的长宽度都比 B 长宽大时，则允许将 B 排列放在 A 上面。现在有一组规格的书籍，书籍叠放时要求书籍不能做旋转，请计算最多能有多少个规格书籍能叠放在一起。

输入格式

输入为一个二维数组，每个元素表示一本书的长度和宽度。

例如：

表示总共 本书籍，第一本长度为 宽度为 ；第二本书长度为 宽度为 ，依次类推，最后一本书长度为 宽度为 。

输出格式

输出一个整数，表示最多能叠放的书籍数量。

样例输入

[[20,16],[15,11],[10,10],[9,10]]

样例输出

3

数据范围

• 书籍的长宽为正整数，范围在
• 书籍数量范围在

题解

这道题目本质上是"最长递增子序列"(LIS)问题的二维变形，也被称为"俄罗斯套娃信封问题"。

在一维的最长递增子序列中，我们要找的是数组中递增的元素序列。而在这个问题中，我们要找的是二维平面上点的"递增"序列，其中"递增"的定义是：一个书籍的长和宽都要大于另一个书籍。

解决这个问题的核心思路是将二维问题转化为一维问题。方法如下：

1. 先按照一个维度（如长度）升序排序
2. 如果长度相同，则按另一个维度（宽度）降序排序
3. 然后在排序后的数组中求宽度的最长递增子序列

为什么要按长度升序排序然后对于长度相同的情况按宽度降序排序？

• 按长度升序排序确保了在选择书籍时长度是递增的
• 对于长度相同的书籍，按宽度降序排序是为了避免在宽度计算LIS时选择长度相同的书籍

这样排序后，我们只需要关注宽度的递增性，因为长度已经通过排序保证了递增。对于长度相同的书籍，由于按宽度降序排序，它们的宽度必然不是递增的，因此不会在同一个递增子序列中出现。

对于求解最长递增子序列，可以使用动态规划和二分查找的优化方法，时间复杂度为O(n log n)。

整体算法步骤：

1. 将书籍按长度升序、宽度降序排序
2. 提取所有书籍的宽度形成新数组
3. 对宽度数组求最长递增子序列
4. 返回最长递增子序列的长度

这个方法的时间复杂度是O(n log n)，其中n是书籍的数量。排序需要O(n log n)时间，而最长递增子序列的计算也需要O(n log n)时间。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入获取
books = eval(input())

def longest_increasing_subsequence(nums):
    """计算最长递增子序列的长度"""
    if not nums:
        return 0
    
    # dp[i]表示长度为i+1的递增子序列的末尾元素的最小值
    dp = [nums[0]]
    
    for i in range(1, len(nums)):
        # 如果当前数大于dp中的最后一个元素，直接添加
        if nums[i] > dp[-1]:
            dp.append(nums[i])
            continue
        
        # 如果当前数小于dp中的第一个元素，替换第一个元素
        if nums[i] < dp[0]:
            dp[0] = nums[i]
            continue
        
        # 二分查找：找到dp中第一个大于等于nums[i]的位置
        left, right = 0, len(dp) - 1
        while left < right:
            mid = (left + right) // 2
            if dp[mid] < nums[i]:
                left = mid + 1
            else:
                right = mid
        
        # 替换该位置的元素
        dp[left] = nums[i]
    
    return len(dp)

def max_stack_books(books):
    # 按长度升序排序，长度相同按宽度降序排序
    books.sort(key=lambda x: (x[0], -x[1]))
    
    # 提取所有书的宽度
    widths = [book[1] for book in books]
    
    # 计算宽度的最长递增子序列
    return longest_increasing_subsequence(widths)

# 调用函数并输出结果
print(max_stack_books(books))

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 计算最长递增子序列的长度
int longestIncreasingSubsequence(const vector<int>& nums) {
    if (nums.empty()) return 0;
    
    // dp[i]表示长度为i+1的递增子序列的末尾元素的最小值
    vector<int> dp;
    dp.push_back(nums[0]);
    
    for (int i = 1; i < nums.size(); i++) {
        // 如果当前数大于dp中的最后一个元素，直接添加
        if (nums[i] > dp.back()) {
            dp.push_back(nums[i]);
            continue;
        }
        
        // 如果当前数小于dp中的第一个元素，替换第一个元素
        if (nums[i] < dp[0]) {
            dp[0] = nums[i];
            continue;