public class StackNSum {
private final Stack<Integer> ints = new Stack<>();
private final Stack<Integer> sums = new Stack<>();
public StackNSum() {
sums.push(0);
}
public void push(final int number) {
sums.push(number + sums.peek());
ints.push(number);
}
public int ksum(final int k) {
// ints.size() - k < 0 need to be handled
return sums.peek() - sums.get(ints.size() - k);
}
}
2条答案
按热度按时间lymnna711#
除了实际值之外,还添加第二个变量来跟踪当前部分和。这样,得到顶部
k
元素的和就简单地由下式给出:ig9co6j12#
我假设你在这里使用整数。您可以将位置
i
的堆栈的总和存储在位置i + 1
的不同sum
堆栈中(sum
堆栈最初包含值0
,因为它是加法的中性元素)。当将一个int元素压入堆栈时,你可以通过添加新的总和来更新
sum
堆栈(只需添加你的int值和sum
堆栈的当前顶部值)。计算顶部
k
元素的总和可以通过从sum
堆栈中的顶部总和值中减去k + 1
总和值来实现。下面是一个示例: