Problem description
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
The MinStack class:
Min Stack()initializes the stack objectvoid push(int val)pushes the elementvalonto stackvoid pop()removes the element on the top of the stackint top()get the top element of the stackint getMin()retrieves the minimum element in the stack
Example:
Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output:
[null,null,null,null,-3,null,0,-2]
Normal method
The easy approach is to add a stack to store the minimum value of each element as the top of the stack in addition to the stack that stores the data.
class MinStack {
private Deque stack;
private Deque minStack;
public MinStack() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
minStack.push(Math.min(val, minStack.peek()));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
No extra space approach
What if we do not want(allowed) to use extra space to store the min value(minStack)?
Only store the difference in the stack! And store only one extra variable minValue.
Push to stack:
When the stack is empty, just store it, and assign it to minValue.
If the stack is not empty, we calculate the difference between the val and the minValue: diff=val-minValue, store it into the stack.
-
If the difference(
diff) bigger than or equal to zero:diff>=0, then the entered value is greater than or equal to the minimum value in the stack, no need to updateminValue. -
If the difference(
diff) is negative, then the entered value is less than minimum value in the stack, update theminValue.
Now let’s consider pop operation.
Pop from stack
When the stack is empty, operation fails.
If the stack is not empty.
-
If the peek value is non-negative. Then it doesn’t affect the
minValue, just pop it. -
If the peek value is negative. So we updated the
minValuewhen pushing the value that make this peek difference, and theminValueis that val we want push to stack(call itnew_minValue=val). So theold_minValuebefore push that element into stack should beold_minValue=new_minValue-diff.
top
Similar to pop.
If the stack is not empty:
- If the peek value is non-negative. Then
val=peekVall(diff)+minValue - If the peek value if negative. Then
val=minValue.
min value
If the stack is not empty, return minValue.
It should be noticed that the differ operation may produce big integer that int can’t hold. Use Long or BigInteger instead.
Code as follows:
class MinStack {
private Deque diffStack;
private int minValue;
public MinStack() {
diffStack = new LinkedList<>();
minValue = -1;
}
public void push(int val) {
if (diffStack.isEmpty()) {
diffStack.push(0L);
minValue = val;
} else {
diffStack.push(Long.valueOf(val) - minValue);
minValue = Math.min(minValue, val);
}
}
public void pop() {
Long diff = diffStack.pop();
if (diff < 0) {
minValue = (int) (minValue - diff);
}
}
public int top() {
Long diff = diffStack.peek();
return diff >= 0 ? (int) (diff + minValue) : minValue;
}
public int getMin() {
return diffStack.isEmpty() ? -1 : minValue;
}
}
Original: https://www.cnblogs.com/liuzhch1/p/16403341.html
Author: liuzhch1
Title: LeetCode 155最小栈: 无额外占用空间-储存差值 ｜Min Stack with No extra space-Store as Difference
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/620662/
转载文章受原作者版权保护。转载请注明原作者出处！