剣指offer面接問題30(java版):min関数を含むスタック

welcome to my blog
剣指offer面接問題30(java版):min関数を含むスタック
タイトルの説明
スタックのデータ構造を定義し、スタックに含まれる最小要素を得ることができるmin関数をこのタイプで実現してください(時間複雑度はO(1))
4回目にします.コア:最小値の維持方法stack 2のスタックトップ要素は現在の最小値である.xがstack 2スタックトップ要素より小さい場合、xを押し込む.xがstack 2のスタックトップ要素より大きい場合は、stack 2のスタックトップ要素を押し込む

class MinStack {
     
    private int min;
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
     
        min  = Integer.MAX_VALUE;
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
     
        stack1.push(x);
        //       ,     stack2  ,    min    min,        min
        // if(x
        //     min = x;
        // stack2.push(min);
        
        
        //      ,   stack2   ,   min    ,    min     ,     min   stack2    !
        // if(stack2.isEmpty())
        //     min = x;
        // if(x < min)
        //     min = x;
        // stack2.push(min);
        
        if(stack2.isEmpty()){
     
            stack2.push(x);
        }
        else{
     
            stack2.push(x<stack2.peek()? x:stack2.peek());
        }
    }
    
    public void pop() {
     
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
     
        return stack1.peek();
    }
    
    public int min() {
     
        return stack2.peek();
    }
}

/**
 * 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.min();
 */

メモ

スタックStack s=new Stack()を宣言して初期化する.一般的に汎用を追加するか、デフォルトの要素タイプがObject

であるか

s.pedk():スタックトップ要素を表示しますが、

はポップアップされません.
構想

は補助スタックを作成し、主スタックの最小値のみを格納し、例

を挙げる.

メインスタック:3,4,5,5,5,6,1,2,7

補助スタック:3,3,3,3,3,1,1,

3回目、s 2は毎回pushではなく、push操作の流れを減らしたが、pop操作の流れを増やす

import java.util.Stack;

public class Solution {
     

    Stack<Integer> s1 = new Stack<Integer>();
    Stack<Integer> s2 = new Stack<Integer>();
    int min = Integer.MAX_VALUE;
    public void push(int node) {
     
        s1.push(node);
        if(node<min){
     
            s2.push(node);
            min = node;
        }
    }
    
    public void pop() {
     
        if(s1.pop()==s2.peek())
            s2.pop();
    }
    
    public int top() {
     
        return s1.peek();
    }
    
    public int min() {
     
        return s2.peek();
    }
}

2回目は、補助スタックs 2をよく使います

import java.util.Stack;

public class Solution {
     
    /*
           
    s1    
    s2       
    s2     ,      ,                    ;                          
    
           push pop  
    */
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();
    public void push(int node) {
     
        s1.push(node);
        if(s2.isEmpty())
            s2.push(node);
        else{
     
            int temp = node < s2.peek()? node:s2.peek();
            s2.push(temp);
        }
    }
    
    public void pop() {
     
        s1.pop();
        s2.pop();
    }
    
    public int top() {
     
        return s1.peek();
    }

    public int min() {
     
        return s2.peek();
    }
}

2回目は、s 2のスタックトップに毎回アクセスすることなく、グローバル変数を持って最小値を記録することができます.

import java.util.Stack;

public class Solution {
     
    /*
           
    s1    
    s2       
    s2     ,      ,                    ;                          
    
           push pop  
    */
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();
    int min = Integer.MAX_VALUE;
    public void push(int node) {
     
        s1.push(node);
        if(node < min)
            min = node;
        s2.push(min);
    }
    
    public void pop() {
     
        s1.pop();
        s2.pop();
    }
    
    public int top() {
     
        return s1.peek();
    }

    public int min() {
     
        return s2.peek();
    }
}

import java.util.Stack;

public class Solution {
     

    Stack<Integer> s = new Stack<Integer>();
    Stack<Integer> assistS = new Stack<Integer>();
    int minV = Integer.MAX_VALUE;
    public void push(int node) {
     
        s.push(node);
        if(minV > node)
            minV = node;
        assistS.push(minV);
    }
    
    public void pop() {
     
        s.pop();
        assistS.pop();
    }
    
    public int top() {
     
        return s.pop();
    }
    
    public int min() {
     
        return assistS.peek();
    }
}