leetcode
leetcode 2051 ~ 2100
你能拿走的最大图书数量

你能拿走的最大图书数量

难度:

标签:

题目描述

代码结果

运行时间: 174 ms, 内存: 36.3 MB


/*
题目思路:
使用Java Stream进行排序和遍历。我们仍然需要将两个数组排序,然后使用双指针的方法来匹配学生和书。
通过stream我们可以更简洁地实现数组的排序和遍历。
*/
import java.util.Arrays;
public class Solution {
    public int maxBooks(int[] books, int[] students) {
        Arrays.sort(books);
        Arrays.sort(students);
        int[] i = {0};
        int[] j = {0};
        int[] maxBooks = {0};
        while (i[0] < books.length && j[0] < students.length) {
            if (books[i[0]] <= students[j[0]]) {
                maxBooks[0] += books[i[0]];
                i[0]++;
                j[0]++;
            } else {
                j[0]++;
            }
        }
        return maxBooks[0];
    }
}

解释

方法:

这个题解使用了动态规划和单调栈的技巧来解决问题。首先,我们使用一个数组 dp 来存储以每个位置结尾时能拿走的最大图书数量。为了计算 dp[i],我们需要找到最左边的位置 j,使得在 j 到 i 之间的图书数量能形成一个连续递增序列。为了快速找到这样的 j,我们可以使用一个单调递增栈来维护一个递增序列,并使用一个辅助数组 firstJ 来记录每个位置 i 左边第一个满足条件的位置 j。然后,根据 j 到 i 之间的图书数量和 books[i] 的值,我们可以分两种情况计算 dp[i]。最后,返回 dp 数组中的最大值即为结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么需要使用单调栈来维护递增序列?这种数据结构在解决这个问题中起到了什么核心作用?
单调栈用于维护一个递增序列,其核心作用在于快速地找到对于每个位置i,左侧第一个满足条件的位置j,使得在 j 到 i 之间的图书序列能构成连续递增。这样的处理可以减少重复的比较和计算,提高算法的效率。在这个问题中,单调栈帮助我们维持一个递增的状态,以便于快速定位和更新dp数组。
🦆
单调栈中元素的出栈条件是`nums[stack[-1]] > nums[i]`,这里的比较逻辑是基于什么考虑?
这个出栈条件基于的是我们需要维持栈内元素在`nums`数组中严格单调递增的特性。`nums`数组是通过`books[i] - i`计算得到的,所以这个比较逻辑是为了保证能找到每个位置i左边的第一个j,使得`nums[j] < nums[i]`。当栈顶元素的值大于当前元素值时,栈顶元素不再满足作为i的满足条件的j的要求,因此需要出栈。
🦆
在计算`dp[i]`时,依据何种规则选择是使用`r * (r + 1) // 2`或者`(tou + r) * count // 2 + dp[j]`的计算方式?
选择计算方式基于i与j之间的距离(count)与books[i]的值(r)。如果count(即i与j之间的位置数)大于等于r,则可以直接使用`r * (r + 1) // 2`计算,因为可以从1累加到r。如果count小于r,则不能直接从1加到r,这时需要计算从`tou`(即r - count + 1)加到r的和,再加上`dp[j]`的值来得到`dp[i]`。
🦆
数组`firstJ`的作用是记录什么?它如何影响`dp`数组的计算?
数组`firstJ`记录对于每个位置i,其左侧第一个满足`nums[j] < nums[i]`的位置j。这个信息是用来确定从哪里开始可以形成一个有效的连续递增序列,从而影响`dp[i]`的计算。知道这个位置j后,可以根据j到i的距离和books[i]的值决定如何计算`dp[i]`,从而有效地利用之前计算的结果(通过`dp[j]`),使得整体解决方案更加高效。

相关问题