关于leetcode个人解题总结:刷题7最小栈

Leetcode：155. 最小栈

办法 1:

关键点：定义两个栈 st 和 stMin，st 寄存所有元素，stMin 寄存最小值。

压入：

行将入栈的元素如果 val<stMin.peek()，则将 val 压入 stMin，如果 val>=stMin.peek()，将 stMin 栈顶元素再次压入 stMin，无论什么状况都要把 val 压入 st。

弹出：

st 和 stMin 别离弹出元素即可。

class MinStack {
    Stack<Integer> st;
    Stack<Integer> stMin;
    /** initialize your data structure here. */
    public MinStack() {st = new Stack<Integer>();
        stMin = new Stack<Integer>();}
    
    public void push(int val) {st.push(val);
        if(stMin.isEmpty()){stMin.push(val);
        }else if(val < getMin()){stMin.push(val);
        }else{stMin.push(stMin.peek());
        }
    }
    
    public void pop() {if(st.isEmpty()){return;}else{st.pop();
            stMin.pop();}
    }
    
    public int top() {if(st.isEmpty()){return -1;}else{return st.peek();
        }
    }
    
    public int getMin() {if(stMin.isEmpty()){return -1;}else{return stMin.peek();
        }
    }
}

办法 2:

1. 压栈

如果 stMin 是空的，则将 val 压入 stMin; 如果 stMin 不为空且 val<=stMin.peek()，也将 val 压入栈中。st 无论哪种状况都压入 val。

2. 出栈

st 栈无论哪种状况都把元素弹出。如果 st 弹出的值等于 stMin 的栈顶元素时，stMin.pop() 把栈顶元素弹出。

class MinStack {
    Stack<Integer> st;
    Stack<Integer> stMin;
    /** initialize your data structure here. */
    public MinStack() {st = new Stack<Integer>();
        stMin = new Stack<Integer>();}
    
    public void push(int val) {st.push(val);
        if(stMin.isEmpty()){stMin.push(val);
        }else if(val <= getMin()){stMin.push(val);
        }
    }
    
    public void pop() {if(st.isEmpty()){return;}else{if(getMin() == st.peek()){stMin.pop();
            }
            st.pop();}
    }
    
    public int top() {if(st.isEmpty()){return -1;}else{return st.peek();
        }
    }
    
    public int getMin() {if(stMin.isEmpty()){return -1;}else{return stMin.peek();
        }
    }
}