欢迎光临
我们一直在努力

Qwen3-Max LintCode 3894 · 能拿走的最大图书数量 public long maximumBooks(int[] books)

LintCode 3894 · 能拿走的最大图书数量 是一道 单调栈 + 动态规划 的经典题目,难度为 Hard。

📚 题目描述(简化)

你面前有一排书架,books[i] 表示第 i 个书架上的图书数量。

你从左到右依次经过每个书架,在每个书架上最多可以拿走若干本书,但必须满足:

你拿走的书的数量必须严格小于前一个书架上拿走的数量(即:拿书数量序列严格递减)。

更准确地说:如果你在位置 i 拿了 x 本书,那么在位置 i-1 必须拿了 至少 x+1 本。

但注意:你也可以跳过某些书架不拿书(即拿 0 本),但一旦开始拿,就要满足递减约束。

✅ 目标:最大化你能拿走的图书总数。

⚠️ 注意:不是子数组,而是子序列,但拿书的位置必须是连续的? ❌ 不!题目允许非连续,但拿书数量必须随索引递增而严格递减。

然而,正确理解(来自官方题意):

你选择一个连续的子数组 [l, r],然后从右到左(或从左到右)拿书,使得:

  • 在位置 r 最多拿 books[r] 本
  • 在位置 r-1 最多拿 min(books[r-1], books[r] + 1) 本
  • …
  • 在位置 i 最多拿 min(books[i], books[i+1] + 1) 本

💡 即:从右往左,每个位置拿的数量不能超过右边位置 + 1,也不能超过自身库存

这等价于:找一个连续区间,使得从右端点向左,拿书数形成一个“受限递增”序列(向左看是递减)

✅ 正确模型(标准解法依据)

你选择一个右端点 i,然后向左延伸,定义 dp[i] = 以 i 为右端点能拿到的最大图书数。

在位置 i,你最多拿 books[i] 本。 在位置 i-1,你最多拿 min(books[i-1], books[i] + 1) 本, 在位置 i-2,最多 min(books[i-2], books[i-1] + 1, books[i] + 2) 本, …

<

赞(0)
未经允许不得转载:171主机测评 » Qwen3-Max LintCode 3894 · 能拿走的最大图书数量 public long maximumBooks(int[] books)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址