乐趣区

关于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();
        }
    }
}
退出移动版