剣指offer:min関数を含むスタック

タイトル:牛客網
テーマの説明
スタックのデータ構造を定義して、スタックに含まれる最小要素のmin関数(時間複雑度はO(1)とする.
考え方の分析
まず、スタックの配列を列挙して、その特徴を観察します.
Stock
トップ
スター1
トップ
66
スター1
トップ
60
50
スター1
トップ
60
50
50
スター1
トップ
60
50
50
80
スター1
トップ
60
50
50
80
20
スター1
トップ
60
50
50
80
20
0
上の分析によって毎回の圧着時の最小値の変化を分析します.
スタック回数
最小値
1
66
2
50
3
50
4
50
5
20
6
0
現在の圧入値がそのスタックの現在の最小値以下である場合のみ、最小値の変更が必要であることがわかる.
またスタックの様子を観察します.
Stock
トップ
スター1
トップ
60
50
50
80
20
スター1
トップ
60
50
50
80
スター1
トップ
60
50
50
スター1
トップ
60
50
スター1
トップ
66
スター1
トップ
上の分析によって、スタックを出すたびに最小値の変化を分析します.
出荷回数
最小値
1
20
2
50
3
50
4
50
5
66
6
現在のスタックの値がそのスタックの現在の最小値に等しい場合のみ、最小値を変更する必要があることが分かります.
締め括りをつける
本題構造の2つのスタック(stackとmin)に対して、スタックは圧入されたデータを格納するために使用され、minは各セグメントの最小値を保存するために使用される.分析によって、スタックに素子を押し込む時に、スタック内に要素(空スタック)がない場合、直接minに押し込むと、押し込んだ要素とminスタックのトップ要素との関係が判断されることが分かります.すなわち、この元素がminに等しいスタックトップ要素より小さい場合、minに押し込む.逆にスタックに入れない.Stckが要素をイジェクトする時、ポップアップ要素の値がminの現在のスタックトップ要素に等しい場合、minの現在のスタックトップ要素がイジェクトされる.
コードの実装

import java.util.Stack;

public class Solution {
    private Stack stack = new Stack<>();
    private Stack min = new Stack<>();
    
    public void push(int node) {
        if (this.stack.empty() || node <= min.peek()) {
            min.push(node);
        }
        this.stack.push(node);
    }
    
    public void pop() {
        if (this.stack.pop() == min.peek()) {
            min.pop();
        }
    }
    
    public int top() {
        return this.stack.peek();
    }
    
    public int min() {
        return this.min.peek();
    }
}