【最小スタック】最小スタックの実現と最適化

さいしょうスタック
極小スタックを実現し,一歩一歩最適化し,余分な空間O(N)からO(1)に至る.push,pop,top,getMinはいずれもO(1)時間である.
1最小値を1つの最小スタックで格納
1.1要点:

スタック、dataはデータを格納し、minValueは最小値を格納します.

pushの場合、dataは直接pushのデータである.minValueは現在の最小値を直接入れます.(minValueには最適化があり、pushのデータが現在の最小値より大きい場合、minValueに最小値の挿入を行わないことができます.最小値以下であれば、最新の最小値pushをスタックminValueに入れる必要があります.

popの場合、dataは直接popにデータを出力する.また、minValueを更新し、更新するポリシーはpushの最適化に対応するポリシーであるpopから出た数であり、==現在の最小値であれば、minValueをpop回行う必要がある.

getMin:スタックminValueのtop要素を直接戻せばよい.

top:スタックdataのtop要素を直接戻せばよい.

1.2複雑度とコード
空間消費量O(N)、O(1)への最適化方法.

class MinStack1 {
     stackdata ;
     stackminValue;
     void push(int x) {
        data.push(x);
        if (minValue.empty() || x <= minValue.top())
            minValue.push(x);
    }

     void pop() {
        int value = data.top();data.pop();
        if (value == minValue.top())
            minValue.pop();
    }

   int top() {
        return data.top();
    }

     int getMin() {
        return minValue.top();
    }
};

2最適化空間複雑度からO(1)
最小スタックの実装を1つのスタックでのみ実現するにはどうすればいいですか?

スタックは、元のデータのみを格納することはできません.差分値(通信原理の差分符号化と同様)を格納する必要があります.

は、スタックの最小値を1つの変数で計算する.

は簡単な例で構想を探求する.

2.1図
スタック順序:2,1,3,4,−2,0,−2 diffスタックの計算=data - minスタックのdata
最小値
 
diffスタック
最小値min
2
2
  0
2
1
1
 
-1
1
3
1
 
2
1
4
1
 
3
1
-2
-2
 
-3
-2
0
-2
 
2
-2
-2
-2
 
0
-2 top:diffスタックに基づいてスタックトップtopの要素を復元するにはどうすればいいですか?push:min最小値をどのように更新しますか?pop:minの最小値をどのように維持しますか?
2.2コード
注意:最初のスタックdiffの特殊な処理.

class MinStack3 {
    stackdiff;
    int minValue;
	
    void push(int x) {
        if (diff.empty()) {
            minValue = x;
            diff.push(0);
        } else {
            int compare = x - minValue;
            diff.push(compare);
            minValue = compare < 0 ? x : minValue;
        }
    }

    void pop() {
        int top = diff.top();
        minValue = top < 0 ? (minValue - top) : minValue;
        diff.pop();
    }

    int top() {
        int top = diff.top();diff.pop();
        return top > 0 ? top + minValue : minValue;
    }

    int getMin() {
        return minValue;
    }
};

 
致命的な欠点:差分値を格納するため、オーバーフローの可能性のある問題を解決できません.
変換元:https://www.cnblogs.com/byrhuangqiang/p/4682354.html