本文共 1136 字,大约阅读时间需要 3 分钟。
文章作者:Tyan
博客: | |Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack.Example:
MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> Returns -3.minStack.pop();minStack.top(); --> Returns 0.minStack.getMin(); --> Returns -2.
主要是模拟写一个最小栈。要注意push时可能会输入null。需要使用双栈实现,一个保存数据,一个保存最小值。由于随着数据出栈,最小值是不断变化的,因此需要一个最小值栈来保存最小值。
class MinStack { private Stackstack = new Stack<>(); private Stack minStack = new Stack<>(); public void push(int x) { if(minStack.isEmpty() || x <= minStack.peek()) { minStack.push(x); } stack.push(x); } public void pop() { if(stack.peek().equals(minStack.peek())) { minStack.pop(); } stack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); }}
转载地址:http://pdwui.baihongyu.com/