C++でO(1)時間・O(1)の追加メモリでスタックの最大値を取得する方法

問題の概要

スタック内の最大要素を常に把握できるスタックを実装したいとします。最大値の取得はO(1)時間で行える必要があり、さらに制約として、追加で使用できる記憶領域もO(1)に限定されます。つまり、最大値専用のもう一つのスタックや配列を用意するような、O(n)の追加メモリを消費する手法は使えません。

アルゴリズムの考え方

ユーザー定義のスタッククラスを作成し、現在の最大値をメンバ変数として保持します。新しい最大値が挿入される際には、スタック本体には変換後の値を格納することで、追加メモリなしで最大値を復元できるようにします。各操作は次のように動作します。

• peek操作： 先頭要素が現在の最大値より大きい場合は、エンコードされた値が格納されていることを意味するため、最大値を返します。それ以外は先頭要素をそのまま返します。
• pop操作： 先頭要素が最大値より大きい場合は、取り出されるのは最大値だったことになるため、最大値を出力し、最大値を「2×max − 先頭要素」で復元・更新します。それ以外は先頭要素をそのまま返します。
• push操作： 挿入するデータxが現在の最大値より大きい場合は、スタックには「2×x − max」をプッシュし、最大値をxに更新します。それ以外はxをそのままプッシュします。

サンプルコード（C++）

#include <iostream>
#include <stack>
using namespace std;
class CustomStack {
    stack<int> stk;
    int stack_max;
    public:
    void getMax() {
        if (stk.empty())
            cout << "Stack is empty"<<endl;
        else
            cout << "Maximum Element in the stack is: "<< stack_max <<endl;
    }
    void peek() {
        if (stk.empty()) {
            cout << "Stack is empty ";
            return;
        }
        int top = stk.top(); // 先頭要素
        cout << "Top Most Element is: "<<endl;
        (top > stack_max) ? cout << stack_max : cout << top;
    }
    void pop() {
        if (stk.empty()) {
            cout << "Stack is empty"<<endl;
            return;
        }
        cout << "Top Most Element Removed: ";
        int top = stk.top();
        stk.pop();
        if (top > stack_max) {
            cout << stack_max <<endl;
            stack_max = 2 * stack_max - top;
        } else
            cout << top <<endl;
        }
        void push(int element) {
            if (stk.empty()) {
            stack_max = element;
            stk.push(element);
            cout << "Element Inserted: " << element <<endl;
                return;
        }
        if (element > stack_max) {
            stk.push(2 * element - stack_max);
                stack_max = element;
        } else
            stk.push(element);
        cout << "Element Inserted: " << element <<endl;
    }
};
int main() {
    CustomStack stk;
    stk.push(4);
    stk.push(6);
    stk.getMax();
    stk.push(8);
    stk.push(20);
    stk.getMax();
    stk.pop();
    stk.getMax();
    stk.pop();
    stk.peek();
}

実行結果

Element Inserted: 4
Element Inserted: 6
Maximum Element in the stack is: 6
Element Inserted: 8
Element Inserted: 20
Maximum Element in the stack is: 20
Top Most Element Removed: 20
Maximum Element in the stack is: 8
Top Most Element Removed: 8
Top Most Element is:
6

仕組みの解説

このアルゴリズムの鍵は、新しい最大値を挿入するときにスタックへ格納する「2×新しい最大値 − 旧最大値」という値にあります。この値は必ず新しい最大値より大きくなるため、pop時に「先頭要素 ＞ 現在の最大値」という条件で「ここに元の最大値が隠れている」ことを検出できます。復元は「2×現在の最大値 − 先頭要素」で行えば、直前の旧最大値が正確に計算し直されます。

この工夫により、補助スタックや配列などの追加データ構造を使わずに、push・pop・peek・getMaxのすべての操作をO(1)時間で実行でき、追加メモリも最大値を保持する整数1つ分（O(1)）で済みます。なお、大きな値を扱う場合は「2×max」の計算でオーバーフローが発生する可能性があるため、実運用では適切なデータ型（例えば long long など）を選択することを推奨します。