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數(shù)據(jù)結(jié)構(gòu)進(jìn)行計(jì)算。但是要進(jìn)行記錄最小值元素就應(yīng)該使用另外的一個(gè)stack進(jìn)行處理。當(dāng)程序使用pop運(yùn)算時(shí)，stack和minstack如果是排出的同一個(gè)元素則應(yīng)該將該元素從兩個(gè)stack中同時(shí)排除。 update: 有人問(wèn)我，為什么push方法中要使用equals方法，而不能使用 ==，因?yàn)镮nteger是引用類(lèi)型的數(shù)據(jù)，引用類(lèi)型的數(shù)據(jù) == 表示指向同一個(gè)地址，而非表示值相同。
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(); */新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
