LintCode 12. Min Stack 原创Java参考解答

LintCode 12. Min Stack 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/min-stack/

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Notice

min operation will never be called if there is no number in the stack.

Example

push(1)
pop()   // return 1
push(2)
push(3)
min()   // return 2
push(1)
min()   // return 1

解题思路

题目是建一个能以O(1)时间查找栈中最小数的栈。

  • 此题只需额外地建一个Stack来额外记录当前栈中的最小数即可。

参考代码

public class MinStack { 
    private Stack<Integer> stack1; 
    private Stack<Integer> stack2; 
    public MinStack() { 
        stack1 = new Stack<>(); 
        stack2 = new Stack<>(); 
    } 
 
    public void push(int number) { 
        stack1.push(number); 
        if (!stack2.isEmpty()) { 
            stack2.push(Math.min(stack2.peek(), number)); 
        } else { 
            stack2.push(number); 
        } 
    } 
 
    public int pop() { 
        if (stack1.isEmpty()) { 
            throw new NoSuchElementException(); 
        } 
        stack2.pop(); 
        return stack1.pop(); 
    } 
 
    public int min() { 
        return stack2.peek(); 
    } 
} 

相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。