首页 > 代码库 > 155. Min Stack
155. Min Stack
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.
思路：看起来很简单的一道题，犯了好多错误。用两个stack，一个用来存输入的数字，一个用来存最小的数字。
if(s2.isEmpty()||x<=s2.peek())
{
s2.push(x);
}
peek之前一定要判断empty。
还有一个问题是s1 pop之后要更新s2。如果s2最小值和s1的pop值一样，更新s2.
public class MinStack { Stack<Integer> s1; Stack<Integer> s2; /** initialize your data structure here. */ public MinStack() { s1=new Stack<Integer>(); s2=new Stack<Integer>(); } public void push(int x) { s1.push(x); if(s2.isEmpty()||x<=s2.peek()) { s2.push(x); } } public void pop() { if(s1.peek().equals(s2.peek())) { s2.pop(); } s1.pop(); } public int top() { return s1.peek(); } public int getMin() { return s2.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. Min Stack
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。