难度: Hard
Submission
运行时间: 174 ms
内存: 36.3 MB
class Solution:
def maximumBooks(self, books: List[int]) -> int:
n=k=len(books)
dp=[0]*k
dp[0]=books[0]
firstJ = [-1] * n # !对每个i找到左边第一个j 满足 arr[j] - j < arr[i] - i
nums = [num - i for i, num in enumerate(books)] # !对每个位置找到左边第一个比他严格小的数的位置 从右往左维护一个递增的单调栈
stack = []
for i in range(n - 1, -1, -1):
while stack and nums[stack[-1]] > nums[i]:
firstJ[stack.pop()] = i
stack.append(i)
for i in range(1, n):
j = firstJ[i]
r=books[i]
#fen 2种情况处理 j在很远的左侧，，
count =i-j
if count >=r:
#1,2,3,4,5,...r
dp[i]=r*(r+1)//2
else:
#gong count 个数字相加 如，5,4,3， 三个数相加
tou= r - count + 1
he = (tou + r)*count//2
dp[i]=he +dp[j]
return max(dp)
Explain
这个题解使用了动态规划和单调栈的技巧来解决问题。首先，我们使用一个数组 dp 来存储以每个位置结尾时能拿走的最大图书数量。为了计算 dp[i]，我们需要找到最左边的位置 j，使得在 j 到 i 之间的图书数量能形成一个连续递增序列。为了快速找到这样的 j，我们可以使用一个单调递增栈来维护一个递增序列，并使用一个辅助数组 firstJ 来记录每个位置 i 左边第一个满足条件的位置 j。然后，根据 j 到 i 之间的图书数量和 books[i] 的值，我们可以分两种情况计算 dp[i]。最后，返回 dp 数组中的最大值即为结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maximumBooks(self, books: List[int]) -> int:
n = k = len(books)
dp = [0] * k
dp[0] = books[0]
firstJ = [-1] * n # 对每个i找到左边第一个j 满足 arr[j] - j < arr[i] - i
nums = [num - i for i, num in enumerate(books)] # 对每个位置找到左边第一个比他严格小的数的位置 从右往左维护一个递增的单调栈
stack = []
for i in range(n - 1, -1, -1):
while stack and nums[stack[-1]] > nums[i]:
firstJ[stack.pop()] = i
stack.append(i)
for i in range(1, n):
j = firstJ[i]
r = books[i]
count = i - j
if count >= r:
dp[i] = r * (r + 1) // 2
else:
tou = r - count + 1
he = (tou + r) * count // 2
dp[i] = he + dp[j]
return max(dp)
Explore
单调栈用于维护一个递增序列，其核心作用在于快速地找到对于每个位置i，左侧第一个满足条件的位置j，使得在 j 到 i 之间的图书序列能构成连续递增。这样的处理可以减少重复的比较和计算，提高算法的效率。在这个问题中，单调栈帮助我们维持一个递增的状态，以便于快速定位和更新dp数组。
这个出栈条件基于的是我们需要维持栈内元素在`nums`数组中严格单调递增的特性。`nums`数组是通过`books[i] - i`计算得到的，所以这个比较逻辑是为了保证能找到每个位置i左边的第一个j，使得`nums[j] < nums[i]`。当栈顶元素的值大于当前元素值时，栈顶元素不再满足作为i的满足条件的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`记录对于每个位置i，其左侧第一个满足`nums[j] < nums[i]`的位置j。这个信息是用来确定从哪里开始可以形成一个有效的连续递增序列，从而影响`dp[i]`的计算。知道这个位置j后，可以根据j到i的距离和books[i]的值决定如何计算`dp[i]`，从而有效地利用之前计算的结果（通过`dp[j]`），使得整体解决方案更加高效。