description: 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.
题目不难，可以直接使用java中给定的stack数据结构进行计算。但是要进行记录最小值元素就应该使用另外的一个stack进行处理。当程序使用pop运算时，stack和minstack如果是排出的同一个元素则应该将该元素从两个stack中同时排除。 update: 有人问我，为什么push方法中要使用equals方法，而不能使用 ==，因为Integer是引用类型的数据，引用类型的数据 == 表示指向同一个地址，而非表示值相同。
public class MinStack { PRivate Stack<Integer> stack; private Stack<Integer> minStack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<Integer>(); minStack = new Stack<Integer>(); } public void push(int x) { stack.push(x); if (minStack.isEmpty()) { minStack.push(x); } else if (minStack.peek() >= x) { minStack.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(); }}/** * 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(); */新闻热点
疑难解答
