Leetcode C++《热题Hot 100-9》155.さいしょうスタック

Leetcode C++《热题Hot 100-9》155.さいしょうスタック

タイトルはpush,pop,top操作をサポートし,定数時間内に最小要素を検索できるスタックを設計した.push(x)-要素xをスタックにプッシュします.pop()–スタックトップの要素を削除します.top()–スタックトップ要素を取得します.getMin()–スタック内の最小要素を取得します.

例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> は、-3を返します.minStack.pop(); minStack.top(); --> 0を返します.minStack.getMin(); --> は、-2を返します.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/min-stack著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.

構想

このテーマも比較的簡単で、方案1:2つのスタック、1つのデータスタック、1つの補助minスタック(補助minスタックはデータスタックと同期して更新することができ、minが変化したときに更新することができる)剣指offer 21はmin関数を含むスタック-類似テーマリンク

より不思議なスキーム2:スタックを使用して、外部にmin値を記録し、min値が変化した場合、それをデータスタックに追加する方法は、

を驚かすほど素晴らしいです.

案2-3参考:https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/

さらにいくつかの変種案3:データスタックの大きさは変わらず、外部は1つのmin値を維持し、min値と元のデータの差を記憶し、差は負数でmin値が更新されたことを示す

である.

時間複雑度の3つのスキームはいずれもO(n)であり,空間複雑度を考慮すると最も空間を節約するのがスキーム3であるため,スキーム3

を試してみる.

コード

class MinStack {
public:
    /** initialize your data structure here. */
    //  int        ，     int  ，      long    
    long min;
    stack<long> nums;

    MinStack() {
    }
    
    void push(int x) {
        if (nums.size() == 0) {
           min = x;
           nums.push(x-min);
           return;
        }
        else if (x < min) {
            nums.push(x-min);
            min = x;
        } else {
            nums.push(x-min);
        }
        
    }
    
    void pop() {
        if (nums.top() < 0)
            min = min - nums.top();
        nums.pop();
    }
    
    int top() {
        if (nums.top() < 0)
            return min;
        else {
            return min+nums.top();
        }
    }
    
    int getMin() {
        return min;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */