LeetCodeの問題解決記録の列の最大値

タイトル:
キューを定義して関数max_を実現してください。valueは列の中の最大値を得て、関数max_を求めます。value、push_backとpop_frontの均等償却時間の複雑さはO（1）である。
列が空なら、pop_frontとmax_value 戻り値-1が必要です

public class MaxQueue{

    public MaxQueue(){
        
    }

    public int max_value() {
        //do something
    }
    
    public void push_back(int value) {
        //do something
    }
    
    public int pop_front() {
        //do something
    }
}

以上はLeetCodeが提示したテーマです。つまり、私達自身で一つの列の構築を完成させます。push_を実現する必要がありますbackメソッドはvalueを列の尾部に挿入し、pop_frontメソッドでキューを取り出し、max_valueはキューの最大値を返しますが、値を削除しません。
その中には時間の複雑さが要求されています。各方法の均等時間の複雑さをO（1）に変えます。これは本題の唯一の難点です。他の問題は全部意味があります。
このテーマを解決するためにダブルリストモードを使いました。

public class MaxQueue{

    private List queue;//        
    private List max;//         

    public MaxQueue(){
        queue = new LinkedList<>();
        max = new LinkedList<>();
    }
    //...      
}

多くの子供たちが、なぜリストで最大値を保存するのかを聞いて、直接intを使えばいいのではないですか？
しかし、事情は簡単ではないですね。例えば、私は{5,4,3,2,1}を順番に列に入れます。この時はmax_を呼び出します。value方法はどれぐらい戻るべきですか？
パートナー：この時は5に戻るべきです。
はい、確かに帰りました。でももし私が一度ポップを呼んだら？front、そして一回max_を呼び出します。value方法は、この時どれぐらい戻るべきですか？
パートナー：元の列｛5，4，2，1｝は、列を外れたら｛4，3，2，1｝になります。この時の最大値は4です。
間違っていません。ここではintタイプだけで最大値を記憶しておくと、列を出る時にはmax_が発生します。value歪みますね
リトルパートナー：listはどのようにして最大値が歪んでいないことを保証しますか？
秘訣はピューシャにありますバック方法で：

public class MaxQueue{
    //...      
    public void push_back(int value) {
        queue.add(value);
        while(max.size() > 0 && max.get(max.size()-1) < value){
            max.remove(max.size()-1);
        }
        max.add(value);
    }
    //...      
}

仲間：what？コメントが一つもないですが、これはどういう意味ですか？
焦らないでください。いくつかの例を挙げて原理を説明します。たとえば:
{5,4}この列の最大値はいくらですか？
仲間：5
それはポップを通してfront方法でキューの先を取り出したらどうなりますか？
仲間：4！ダブルリストの方法で、maxのセットをソートすればいいと分かりました。そして、リアルタイムで最大値を知ることができます。
そうです。しかし、問題は時間の複雑さをO（1）と要求しています。どの順序付けアルゴリズムも時間の複雑さはO（1）では完成できません。
パートナー：アルゴリズムを並べ替えないと、どの値が一番大きいかどうやって決めますか？
もちろんいいです。私たちは列ごとに入隊する時に一回比較すればいいです。
例えば、queue={5}この時のmax={5}は、行列の中に一つの値しかないので、この値は絶対最大値です。
その後引き続きデータを追加して入隊します。queue={5,4}この時はmaxの中の既存の値aと新入隊の値bを比較します。
a>bの場合は、max={a，b}aこの公式に基づいて、私達はqueueの中の値を代入して、max={5,4}を得ます。
パートナー：このようなアルゴリズムはキューの値と二つの場合しか適用できないようですが、もし列の値が多いなら？
例えば、queue={5,4,3,6,1}この順番で順番に入隊、出隊します。どう処理すればいいですか？
OKです。まず先ほどの規則に従って歩きます。問題がどこにあるか確認してみます。
1）queue=｛5｝max=｛5｝
2）queue=｛5、4｝max=｛5、4｝
3）queue=｛5、4、3｝max=｛5、4、3｝
4）queue=｛5、4、3、6｝max=｛6｝
5）…
パートナー：ちょっと待ってください。なぜ4歩目のmaxがいきなり6になったのですか？さらに他の値を移動しますか？
hhh、これが行列のルールです。queueの入隊規則は何ですか？
小仲間：新たに加入した値は全部列の最後に追加されます。
じゃチームから出るルールは？
パートナー：各チームの値は、現在の列の先頭、つまり最初に列に入る値です。
そうです。この規則によって、queue={5,4,3,6}の時は、5,4,3がスタックから出ていても、現在の列の最大値は6です。
6の前に並んでいて、6より小さい数字は直接無視できます。6を先に譲って、5、4、3がまだチーム内に残っている状況がないからです。
パートナー：つまり、新しい数Aを追加するごとに、Aとmaxのセットにあるすべての値を比較する必要がありますか？
このような意味です。確かに比較が必要ですが、すべての値と比較するのではありません。
例えば、queue={5,4,10,6,1,2,3,4}、行列がこのような順番であれば、maxの中で最大値をどのように保存すればいいですか？
パートナー：えっと、maxに10を預けたら、10がチームを出た後、残りの数字は6が一番大きいです。6を預けたら、6がチームから出たら4が一番大きいというルールがありますか？
そうです。一つの法則があります。queue={5,4,10,6,1,2,3,4}に赤い数字を表示すると、maxの中で順次保存する値です。
小パートナー：えっと、法則は何ですか？
保管手順説明：
1）queue={5} max={5}5は唯一の数ですから。
2）queue={5,4} max={5,4}5がスタックを出た後、4が最大の数(唯一の数)です。
3）queue={5,4,10} max={10} 10はmaxの他の値よりも大きいし、最後の方です。
4）queue={5,4,10,6} max={10,6}10はまだmaxの中で最大の値ですが、6の前に並んでいます。つまり、10が出ると6が一番大きいということです。
5）queue={5,4,10,6,1} max={10,6,1}原因は上と同じです。10と6は順番に出ます。1は最大値です。
6）queue={5,4,10,6,1,2} max={10,6,2} ここの2は入隊後、1はもう列の最後の方ではなく、10、6が出たら最大の数は2ですよ。
7）queue={5,4,10,6,1,2,3} max={10,6,3} 上と同じように、3が2の位置を取って、チームの中で最後の大きな数になりました。
8）queue={5,4,10,6,1,2,3,4} max={10,6,4} ここに来て4が代わりました。
子供のパートナー：だから、新しい数字Aがチームに入る時は全部maxの中で最後の値Bと比較しますか？B>Aの場合は、Aをmaxの列の最後に追加し、B＜Aの場合はBを除去し、Aを追加する。
そうです。このような意味で、列のmaxのチームヘッドは永遠にqueueの中の最大値です。

//    
public class MaxQueue{

    private List queue;
    private List max;

    public MaxQueue(){
        queue = new LinkedList<>();
        max = new LinkedList<>();
    }

    public int max_value() {
        return max.size() > 0 ? max.get(0) : -1;
    }
    
    public void push_back(int value) {
        queue.add(value);
        while(max.size() > 0 && max.get(max.size()-1) < value){
            max.remove(max.size()-1);
        }
        max.add(value);
    }
    
    public int pop_front() {
        int tmp = -1;
        if(queue.size() > 0){
            tmp = queue.get(0);
            queue.remove(0);
            if(tmp == max.get(0)){
                max.remove(0);
            }
        }
        return tmp;
    }
}