LeetCode 155の最も小さいスタックの3つの実現方法JavaScript

ソースリンク:クリックしてpush、pop、top操作をサポートし、定数時間内で最小要素のスタックを検索することができます.

push(x)–要素xをスタックに押し込む.

ポップ()–スタックトップの要素を削除します.

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.

これは面白い簡単な問題です.私にとってデザイン思想と考え方は中ぐらいの難度の問題になりますが、始めましょう.今回はJavaScriptで書きます.JSという言葉の穴が多いですが、穴に入ってからも十分な楽しみがあります.相手に向かって歩いても練習になります.
解法1getMinの定数レベルの効率を実現するために、スタックは試し得るデータ構造である.minStackという補助スタックを使用して、現在巡回されている局部最小値を保存し、pushの過程で補助スタックトップより大きくない値に遭遇した時、引き続き補助スタックに押し込む.これは部分的な検索保存が極めて小さいので、大域最小の戦略(自分の盲点を取る)を得ることである.popのポップアップの際には、元のデータスタックdataおよび補助スタックminStackのスタックトップ値を比較する必要があり、ちょうどポップアップが最小値である場合には、一緒にポップアップする.コードは以下の通りです

//    
class MinStack {
    constructor(data=[], minStack=[]) {
        this.data = data;
        this.minStack = minStack;
    }
    
    push(x) {
        this.data.push(x);
        if (this.minStack.length === 0 || x <= this.minStack.slice(-1)) {
            this.minStack.push(x);
        }
    }
    
    pop() {
        if (JSON.stringify(this.data.slice(-1)) === JSON.stringify(this.minStack.slice(-1))) {
            this.minStack.pop();
    	}
         this.data.pop();
    }
    
    top() {
        return this.data.slice(-1);
    }
    
    getMin() {
        return this.minStack.slice(-1);
    }
};

解法二
定数時間内で最小値を得るためには,余分な空間複雑さが必要である.上には、極小値を保存するための新しい補助スタックが開かれています.考えてみると、pushデータの間に極小値の情報を伝送することによって、スタックに入ることもできる.具体的にはpushの2回、第1回pushの元のデータ、第2回pushの極小値、もちろんpopの時も2回必要です.現在のデータスタックの下でpopは一回で最小値が得られます.popは第2回目で現在値が得られます.具体的な詳細はこれ以上説明しない.そのために、次のコードを書きます.

class MinStack {
    constructor(minStack=[]) {
        this.minStack = minStack;
    }

    push(x) {
        if (this.minStack.length === 0) {
            this.minStack.push(x);
            this.minStack.push(x);
        } else {
            let curMin = this.minStack.slice(-1);
            this.minStack.push(x);
            if (x < curMin) {
                this.minStack.push(x);
            } else {
                this.minStack.push(curMin);
            }
        }
        
    }
    
    pop() {
        this.minStack.pop();
        this.minStack.pop();
    }

    top() {
        return this.minStack.slice(-2)[0];
    }
    getMin() {
        return this.minStack.slice(-1);
    }
};

解法三
考え方を変えて、チェーンを利用して最小値の属性を保存します.
正直に言って、下のコードもオーディエンスを参考にしてjavascriptに変えて書いています.しかし、この問題を考え始めたばかりの時には、チェーンやフォークなど他のデータ構造で解決しようとしましたが、どうすればいいですか?話が多くないです.コードは以下の通りです.

//        
class Node {
    constructor(val, min, next=null) {
        this.val = val;
        this.min = min;
        this.next = next;
    }
}

class MinStack {
    constructor() {
        this.head = null
    }
    
    push(x) {
        if (this.head === null) {
            this.head = new Node(x, x)
        } else {
            this.head = new Node(x, Math.min(this.head.min, x), this.head);
        }
    }
    
    pop() {
        this.head = this.head.next;
    }

    top() {
        return this.head.val;
    }

    getMin() {
        return this.head.min;
    }
};

これは簡単な問題です.ハハ、自分はまだ太菜です.