1. 问题背景与题目解析
今天我们来拆解LintCode 3894这道经典动态规划题目——"能拿走的最大图书数量"。题目要求我们设计一个算法，计算从书架取书的最大数量，遵循特定规则：当从第i本书开始取时，必须连续取若干本，且每本书的编号必须严格递增1。
题目给出的函数签名是：
public long maximumBooks(int[] books)书架上的书籍排列用一个整数数组books表示，其中books[i]表示第i本书的编号。我们需要找到一种取书策略，使得取出的书籍总数量最大化。
举个例子：
- 输入：[8, 5, 2, 7, 9]
- 解释：最佳取法是取[2,7,9]，因为2+7+9=18是最大值
- 输出：18
2. 动态规划解法核心思路
2.1 状态定义与转移方程
这道题的核心在于发现子问题的最优解如何构成整个问题的最优解。我们定义dp[i]表示以第i本书作为取书序列结尾时能获得的最大书籍数量。
状态转移方程需要考虑两种情况：
- 如果
books[i] > books[i-1]，那么可以把第i本书接在前一个序列后面 - 否则，只能从第i本书开始一个新的序列
具体来说，状态转移方程为：
dp[i] = books[i] + max( dp[j] + sum(books[j+1...i]), 其中j是满足books[k] == books[k+1]-1的最大j )2.2 单调栈优化技巧
直接实现上述DP会导致O(n²)的时间复杂度。我们可以使用单调栈来优化：
- 维护一个栈，保存潜在的最优j值
- 对于每个i，弹出栈顶所有不满足
books[j] < books[i] - (i-j)的元素 - 计算当前dp[i]的值
- 将i压入栈中
这样可以将时间复杂度优化到O(n)。
3. 完整Java实现代码
public long maximumBooks(int[] books) { int n = books.length; long[] dp = new long[n]; Deque<Integer> stack = new ArrayDeque<>(); long res = 0; for (int i = 0; i < n; i++) { while (!stack.isEmpty() && books[stack.peek()] >= books[i] - (i - stack.peek())) { stack.pop(); } if (stack.isEmpty()) { int len = Math.min(books[i], i + 1); dp[i] = (long)(books[i] + books[i] - len + 1) * len / 2; } else { int j = stack.peek(); int len = i - j; dp[i] = dp[j] + (long)(books[i] + books[i] - len + 1) * len / 2; } res = Math.max(res, dp[i]); stack.push(i); } return res; }4. 代码逐行解析
4.1 初始化阶段
int n = books.length; long[] dp = new long[n]; Deque<Integer> stack = new ArrayDeque<>(); long res = 0;n：数组长度dp数组：存储每个位置的最优解stack：单调栈，用于优化查找过程res：记录全局最大值
4.2 主循环逻辑
for (int i = 0; i < n; i++) { while (!stack.isEmpty() && books[stack.peek()] >= books[i] - (i - stack.peek())) { stack.pop(); } // ... }这部分维护单调栈的性质，弹出所有不满足条件的j值。
4.3 计算dp[i]
if (stack.isEmpty()) { int len = Math.min(books[i], i + 1); dp[i] = (long)(books[i] + books[i] - len + 1) * len / 2; } else { int j = stack.peek(); int len = i - j; dp[i] = dp[j] + (long)(books[i] + books[i] - len + 1) * len / 2; }- 当栈为空时，计算从开头到i的序列和
- 否则，基于前一个有效j值计算当前dp值
4.4 更新结果
res = Math.max(res, dp[i]); stack.push(i);每次迭代更新全局最大值，并将当前索引入栈。
5. 算法复杂度分析
- 时间复杂度：O(n)
- 每个元素最多入栈和出栈一次
- 主循环中的while循环总体不会超过n次操作
- 空间复杂度：O(n)
- 需要存储dp数组和单调栈
6. 边界条件与测试用例
6.1 典型测试用例
// 测试用例1 输入：[8,5,2,7,9] 输出：18 (取[2,7,9]) // 测试用例2 输入：[7,0,9,4,6] 输出：16 (取[0,4,6] + 7) // 测试用例3 输入：[1,2,3,4,5] 输出：15 (取全部)6.2 特殊边界情况
- 空数组：返回0
- 单元素数组：返回该元素值
- 所有元素相同：返回任意一个元素值
- 严格递减序列：返回最大值
7. 实际应用场景延伸
这类动态规划+单调栈的组合解法在以下场景也很常见：
- 最大矩形面积问题
- 接雨水问题
- 股票买卖问题
- 字符串匹配中的某些优化场景
掌握这种模式可以解决LeetCode/LintCode上很多hard级别的题目。
8. 常见错误与调试技巧
8.1 整数溢出问题
- 注意累加时可能超出int范围
- 解决方案：使用long类型存储dp值和中间结果
8.2 单调栈维护错误
- 确保弹出条件正确
- 调试技巧：打印栈内容检查是否符合预期
8.3 序列和计算错误
- 等差数列求和公式要写对
- 验证：(首项+末项)*项数/2
9. 算法优化思路进阶
如果题目变为可以跳过任意数量的书（不要求连续取），但取出的书必须编号递增，问题就变成了经典的"最长递增子序列"问题。这种情况下：
- 可以用O(n²)的DP解法
- 或者用O(nlogn)的贪心+二分优化解法
10. 同类题目推荐
- LeetCode 300. 最长递增子序列
- LintCode 76. 最长上升子序列
- LeetCode 84. 柱状图中最大的矩形
- LeetCode 42. 接雨水
- LeetCode 85. 最大矩形
这些题目都使用了类似的动态规划+单调栈优化技巧，建议一起练习以加深理解。
