如何在Java中实现栈的ksum()方法，以O(1)时间返回栈顶k元素之和

要实现O(1)时间返回栈顶k个元素的和，核心思路是维护一个前缀和数组，和ArrayList实现的栈同步更新，用空间换时间。

具体实现步骤 #

• 用两个ArrayList：一个stack存储栈的实际元素，另一个prefixSum存储前缀和（每个元素代表从栈底到当前栈顶的所有元素总和）。
• push操作：
  1. 将新元素添加到stack的末尾。
  2. 计算当前前缀和：如果prefixSum为空，直接添加新元素的值；否则添加prefixSum.getLast() + 新元素，将结果存入prefixSum末尾。
• pop操作：
  同时移除stack和prefixSum的最后一个元素，保证两者长度始终一致。
• ksum()方法：
  1. 先做边界校验：如果k <= 0或者k > stack.size()，可以返回0或者抛出非法参数异常（根据业务需求处理）。
  2. 假设当前栈的大小为n，栈顶k个元素的和 = prefixSum.get(n-1) - (n - k > 0 ? prefixSum.get(n - k - 1) : 0)。

示例说明 #

比如栈中元素依次是[1,2,3,4]，对应的前缀和数组是[1, 3, 6, 10]：

• 当k=2时，栈顶2个元素是3和4，和为7。用公式计算：10 - prefixSum.get(4-2-1) = 10 - 3 =7，结果正确。
• 当k=4时，和就是前缀数组最后一个元素10，直接返回即可。

注意事项 #

• 前缀和建议用Long类型存储，避免元素累加时出现整数溢出问题。
• 必须保证stack和prefixSum的操作完全同步，push/pop时同时更新两个数组，否则会导致计算错误。

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