リンクリストに現在の長さと合計を加えたものを使用することを検討しましたか？各操作について、一定の追加作業で現在の平均を維持できます（リストの長さと合計がわかっていて、すべての操作でこれら2つの値が一定の方法で変更されます）。
唯一の非定数操作は、任意のプレフィックスに定数を追加することです。これは、各数値を調整する必要があるため、プレフィックスのサイズに比例して時間がかかります。
すべての操作を一定（償却）にするには、より多くの作業が必要です。二重リンクリストを使用する代わりに、スタックで配列をバックアップします。i配列の各スロットには、での数値iと、までのすべての要素に追加される定数の両方が含まれるようになりましたi。（「要素11までのすべての要素に3を追加する」と言うと、スロット11には番号3が含まれますが、スロット0〜10は空になります。）これで、新しい要素を追加することを除いて、すべての操作が以前と同じになります。標準の配列倍増トリックが含まれ、キューの最後から最後の要素をポップするときは、（a）そのスロットに定数を追加し、（b）スロットからスロットの定数に定数値を追加する必要がありiますi-1。だからあなたの例のために：
追加0： [(0,0)], sum 0, length 1
付録5： ([(0,0),(5,0)], sum 5, length 2
付録6： [(0,0),(5,0),(6,0)], sum 11, length 3
シーケンスの最初の2つの要素に3を追加します。[(0,0),(5,3),(6,0)], sum 17, length 3
平均5.66を取得します
最後の要素を削除します[(0,0),(5,3)], sum 11, length 2
平均5.5を取得します
最後の要素を削除します[(0,3)], sum 3, length 1
アイデアをおそらくより明確に示すJavaコードを次に示します。
class Averager {
private int sum;
private ArrayList<Integer> elements = new ArrayList<Integer>();
private ArrayList<Integer> addedConstants = new ArrayList<Integer>();
public void addElement(int i) {
elements.add(i);
addedConstants.add(0);
sum += i;
}
public void addToPrefix(int k, int upto) {
addedConstants.set(upto, addedConstants.get(upto) + k);
sum += k * (upto + 1);
// Note: assumes prefix exists; in real code handle an error
}
public int pop() {
int lastIndex = addedConstants.length() - 1;
int constantToAdd = addedConstants.get(lastIndex);
int valueToReturn = elements.get(lastIndex);
addedConstants.set(
lastIndex-1,
addedConstants.get(lastIndex-1) + constantToAdd);
sum -= valueToReturn;
elements.remove(lastIndex);
addedConstants.remove(lastIndex);
return valueToReturn + constantToAdd;
// Again you need to handle errors here as well, particularly where the stack
// is already empty or has exactly one element
}
public double average() {
return ((double) sum) / elements.length();
}
}