The problem for the solution is the cast. Since the possible gap between the current value and the min value could be Integer.MAX_VALUE-Integer.MIN_VALUE;
Solution
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int number) {
stack.push(number);
if (minStack.isEmpty()) {
minStack.push(number);
} else if (Integer.parseInt(minStack.peek().toString()) >= number) {
minStack.push(number);
}
}
public int pop() {
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
return stack.pop();
}
public int min() {
return minStack.peek();
}
}
You can't compare twoIntegerwith a simple == they're objects so most of the time references won't be the same.
There is a trick, with Integer between -128 and 127, references will be the same as autoboxing usesInteger.valueOf()which caches small integers.
因此，可以先用int强制转化。
参考：
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
Stack<Integer> t = new Stack<>();
s.push(-1);
t.push(-1);
System.out.println(s.pop() == t.pop());
s.push(-129);
t.push(-129);
System.out.println(s.pop() == t.pop());
s.push(128);
t.push(128);
System.out.println(s.pop() == t.pop());
}
}
// output:
// true
// false
// false
--
Time: O(1)
Space: O(n)
class MinStack {
Stack<Integer> stack;
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 ((int) minStack.peek() >= x) {
minStack.push(x);
}
}
public void pop() {
int x = stack.pop();
if (!minStack.isEmpty() && x == minStack.peek()) {
minStack.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();
*/
Using One Stack - store difference between x and min
Time: O(1)
Space: O(1)
top() - 如果当前栈顶的对应元素是新的min值，那么 top() 对应 min, 否则对应 stack.peek() + min
push() - 每次存入
public class MinStack {
long min;
Stack<Long> stack;
public MinStack() {
min = Integer.MAX_VALUE;
stack = new Stack<>();
}
public void push(int x) {
stack.push((long)x - min);
min = Math.min(x, min);
}
public void pop() {
min = Math.max(min - stack.pop(), min);
}
public int top() {
return (int)Math.max(stack.peek() + min, min);
}
public int getMin() {
return (int)min;
}
}
Using One Stack with Custom Element Class Object - Store min within each element
Time: O(1)
Space: O(n), extra space for the min value in the custom class object
class MinStack
{
static class Element
{
final int value;
final int min;
Element(final int value, final int min)
{
this.value = value;
this.min = min;
}
}
final Stack<Element> stack = new Stack<>();
public void push(int x) {
final int min = (stack.empty()) ? x : Math.min(stack.peek().min, x);
stack.push(new Element(x, min));
}
public void pop()
{
stack.pop();
}
public int top()
{
return stack.peek().value;
}
public int getMin()
{
return stack.peek().min;
}
}
Using LinkedList Node*
class MinStack {
private Node head;
public void push(int x) {
if(head == null)
head = new Node(x, x);
else
head = new Node(x, Math.min(x, head.min), head);
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
private class Node {
int val;
int min;
Node next;
private Node(int val, int min) {
this(val, min, null);
}
private Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}