155 最小值栈

【题目】

155 最小值栈
155 最小值栈
155 最小值栈

【分析】

一般的栈就具有push()、pop()、top()的功能。getMin()的功能如何在常数时间内实现呢?
155 最小值栈
如果查找的话,至少是线性时间。不符合要求。

【方法一】

使用一个辅助栈,用来保存当前栈中的最小值。执行getMin()操作时,返回辅助栈的栈顶元素即可。

155 最小值栈
代码:

class MinStack {
    Stack<Integer> dataStack;
    Stack<Integer> minStack;

    public MinStack() {
        dataStack = new Stack();
        minStack = new Stack();
    }
    
    public void push(int x) {
        dataStack.push(x);
        if(minStack.empty()==true || minStack.peek()>x){
            minStack.push(x);
        }else{
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        dataStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int getMin() {
        return minStack.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.getMin();
 */

结果:
155 最小值栈

【方法二】

也可以不使用辅助栈,让栈中保存的是<data,min>对,起到辅助栈相同的效果。
155 最小值栈

代码:

class MinStack {
    class Node{
        int data;
        int min;   //保存当前位置的最小值
        Node(int data, int min){
            this.data=data;
            this.min = min;
        }
    }
    Stack<Node> s;

    public MinStack() {
        s = new Stack<>();
    }
    
    public void push(int x) {
        int min =x;
        if(s.empty()==false && x>s.peek().min){
            min = s.peek().min;
        }
        Node node = new Node(x,min);
        s.push(node);
    }
    
    public void pop() {
        s.pop();
    }
    
    public int top() {
        return s.peek().data;
    }
    
    public int getMin() {
        return s.peek().min;
    }
}

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

结果:
155 最小值栈

上一篇:[LeetCode] 155. 最小栈


下一篇:Leetcode(Java)-155. 最小栈