2355：你能拿走的最大图书数量（★★）

力扣第 2355 题

题目

给定一个长度为 n 的 下标从 0 开始 的整数数组 books，其中 books[i] 表示书架的第 i 个书架上的书的数量。

你要从书架 l 到 r 的一个 连续 的部分中取书，其中 0 <= l <= r < n。对于 l <= i < r 范围内的每个索引 i，你从书架 i 取书的数量必须 严格小于 你从书架 i + 1 取书的数量。

返回你能从书架上拿走的书的 最大 数量。

示例 1:

输入: books = [8,5,2,7,9]
输出: 19
解释:
- 从书架 1 上取 1 本书。
- 从书架 2 上取 2 本书。
- 从书架 3 上取 7 本书
- 从书架 4 上取 9 本书
你已经拿了19本书，所以返回 19。
可以证明 19 本是你所能拿走的书的最大数量。

示例 2:

输入: books = [7,0,3,4,5]
输出: 12
解释:
- 从书架 2 上取 3 本书。
- 从书架 3 上取 4 本书。
- 从书架 4 上取 5 本书。
你已经拿了 12 本书，所以返回 12。
可以证明 12 本是你所能拿走的书的最大数量。

示例 3:

输入: books = [8,2,3,7,3,4,0,1,4,3]
输出: 13
解释:
- 从书架 0 上取 1 本书。
- 从书架 1 上取 2 本书。
- 从书架 2 上取 3 本书。
- 从书架 3 上取 7 本书。
你已经拿了 13 本书，所以返回 13。
可以证明 13 本是你所能拿走的书的最大数量。

提示:

• 1 <= books.length <= 105
• 0 <= books[i] <= 105

相似问题：

• 0300：最长递增子序列
• 1800：最大升序子数组和（1229 分）
• 2866：美丽塔 II（2071 分）
• 2865：美丽塔 I（1519 分）

分析

• 假设选了最后一本书 j，往前找第一个下标 i 满足 books[i]<=books[j]-j+i
• 那么 books[:i+1] 是递归子问题，[i+1,j] 是等差 1 的数列
• 令 A[i] 代表 books[i]-i，即转为找上一个更小元素，用单调栈即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maximumBooks(self, books: List[int]) -> int:
        n = len(books)
        A = [x-i for i,x in enumerate(books)]
        L = [-1]*n
        sk = []
        for j,a in enumerate(A):
            while sk and A[sk[-1]]>a:
                sk.pop()
            if sk:
                L[j] = sk[-1]
            sk.append(j)
        f = [0]*(n+1)
        for j,a in enumerate(books):
            i = L[j]
            c = min(a,j-i)
            f[j+1] = f[i+1]+(a+a-c+1)*c//2
        return max(f)

236 ms