如何计算从两个栈数组中取元素至总和≤20的最大次数

问题说明 #

给定两个栈结构数组（仅允许从索引0位置移除元素，即每次只能取数组的第一个有效元素）：

• 数组1有效元素：[5, 1, 1]（忽略占位符-）
• 数组2有效元素：[5, 6, 5, 1, 1, 1]
  要求每次选取一个数组的索引0元素并移除，累加选取元素的总和必须≤20，求最多能选取多少次。

核心思路 #

由于只能从数组头部取元素，每个数组的选取序列必然是其前缀（比如选数组2的k个元素，就是前k个元素的累加和）。我们可以通过预处理前缀和，再组合验证找到最大次数：

1. 分别计算两个数组所有可能的前缀和及对应选取次数
2. 遍历其中一个数组的所有前缀情况，在另一个数组中找到能让总和≤20的最大可选取次数，最终取所有组合的最大值

具体计算 #

1. 计算前缀和与次数 #

• 数组2：
  • 取1个：和=5，次数=1
  • 取2个：和=11，次数=2
  • 取3个：和=16，次数=3
  • 取4个：和=17，次数=4
  • 取5个：和=18，次数=5
  • 取6个：和=19，次数=6
• 数组1：
  • 取1个：和=5，次数=1
  • 取2个：和=6，次数=2
  • 取3个：和=7，次数=3

2. 组合验证找最大值 #

• 当取数组2全部6个元素时，总和为19≤20，剩余可分配总和为1，数组1最小前缀和为5>1，无法再选取，总次数为6
• 其他组合（比如取数组2的5个元素+0个数组1元素，总次数5；或数组1的3个元素+数组2的2个元素，总次数5）均小于6
• 因此最大选取次数为6

大规模数组通用解法 #

对于任意规模的两个数组，可通过以下高效方式实现：

1. 预处理两个数组的前缀和数组，记录每个前缀的累加和与对应次数
2. 将其中一个前缀和数组按累加和升序排序
3. 遍历另一个数组的每个前缀，用二分查找找到另一个数组中最大的前缀和（使得两者之和≤20），计算总次数并更新最大值
   该方法时间复杂度为O(n + m + n log m)（n、m为两数组长度），适合处理大规模数组。

内容的提问来源于stack exchange，提问作者rubikkubika