class MinStack {
int min = Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>();
public void push(int x) {
// only push the old minimum value when the current
// minimum value changes after pushing the new value x
if(x <= min){
stack.push(min);
min=x;
}
stack.push(x);
}
public void pop() {
// if pop operation could result in the changing of the current minimum value,
// pop twice and change the current minimum value to the last minimum value.
if(stack.pop() == min) min=stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
Java accepted solution using one stack


Clever solution. However, beside overhead, this algorithm does not save memory when compare to 2 stacks solution. Basically, the additional push you make when (x <= min) is the same as you push the new min value (i.e., x) to the min stack.
Also, I implemented this algorithm in C++ and got Output Limit Exceeded error.

For your reference, here is my fast and concise AC Java code.
I didn't deal with the case when
MinStack
isempty
, because it will raiseRuntimeError
and should be handled by theStack
class.class MinStack { Stack<Integer> stack = new Stack<>(); int min = Integer.MAX_VALUE; public void push(int x) { if (x <= min) { stack.push(min); min = x; } stack.push(x); } public void pop() { int peek = stack.pop(); if (peek == min){ min = stack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return min; } }

I like your solution.
Let me paste the C++ version here.class MinStack { public: MinStack(): m_min(INT_MAX){} void push(int x) { if(x <= m_min){ m_stack.push(m_min); m_min = x; } m_stack.push(x); } void pop() { if(m_stack.top() == m_min){ m_stack.pop(); m_min = m_stack.top(); m_stack.pop(); } else { m_stack.pop(); } if(m_stack.empty()) m_min = INT_MAX; } int top() { return m_stack.top(); } int getMin() { return m_min; } private: stack<int> m_stack; int m_min; };

@sometimescrazy said in Java accepted solution using one stack:
public void pop() { // if pop operation could result in the changing of the current minimum value, // pop twice and change the current minimum value to the last minimum value. if(stack.pop() == min) min=stack.pop(); }
I am rather confused about this part... I understand the general idea, but how does it work in detail?