https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73098
这里的一个关键是理解为什么是x<=trackMin.top()而不是x<trackMin.top()。加入对于push(x)只有当x<trackMin.top()时，才将x压入trackMin中。
例如压入以下数后：
X.
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.
X. Save space
The idea is to store the gap between the min value and the current value;
The problem for my solution is the cast. I have no idea to avoid the cast. Since the possible gap between the current value and the min value could be Integer.MAX_VALUE-Integer.MIN_VALUE;
public class MinStack {
long min;
Stack<Long> stack;
public MinStack(){
stack=new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()){
stack.push(0L);
min=x;
}else{
stack.push(x-min);//Could be negative if min value needs to change
if (x<min) min=x;
}
}
public void pop() {
if (stack.isEmpty()) return;
long pop=stack.pop();
if (pop<0) min=min-pop;//If negative, increase the min value
}
public int top() {
long top=stack.peek();
if (top>0){
return (int)(top+min);
}else{
return (int)(min);
}
}
public int getMin() {
return (int)min;
}
}
先来说个常规解和他的一个优化,常规解的时间复杂度符合要求,但需要线性的额外空间.
除了题目要求的栈之外新开一个栈,用来记录最小值,每当在原栈中push数据后,与最小值栈中的栈顶元素比较,如果新值较小,则在最小值栈中push新值;否则再次push栈顶元素.
pop的时候,只要将最小值栈也pop一下就行了.
这样,min函数只需要返回最小值栈的栈顶元素即可.
常规解空间上的一个优化:
一般说来,最小值不会每次都需要更新,因此最小值栈里面会有很多重复元素.因此一个简单的优化就是在新值只当<=原最小值时才pushIntoMin,注意这个==的条件是不可少的,这是为了防止在pop的时候错误的pop最小值.pop的是, 当待pop值==最小值时popMinStack, 其他时候不对最小值栈进行pop
下面说一种具有常数空间复杂度的方法:
在这个方法里,只需要额外开一个用于存放当前最小值的变量min即可.因此下面提到的push和pop操作都是对于题目中要求的栈来操作的,当然,这也是这个算法里唯一的栈.
设push的参数为v_push,pop的返回值为v_pop.
先说下整体思路:因为栈中所有元素的值都不会小于当其为栈顶元素时min函数的值,所以在栈中其实只需要保存某元素比相应最小值大出来的值就可以了.而对于最小值更新的位置,栈元素肯定为0,因此可以利用这个位置来保存更多的信息,在这里是更新后前两个最小值的差值,而这个值肯定是非正的.
根据上面的思路,push函数按照如下策略进行:
首先push (v_push-min),如果v_push < min,更新min为v_push.
相应的,pop函数按照如下策略进行(称栈顶元素为top):
如果top >= 0, v_pop = min+top, 如果top < 0, v_pop = min,然后更新min为min-top.
显然,对于min函数来说,只需要返回min空间的内容即可.
与张霄学长交流后,学长也讲了一个类似的方法:
push时候 如果 v_push >= min, v_push 直接入栈， 如果 v_push < min, 那么入栈的是 2 * v_push - min, 然后 min = v_push. 出栈时， 如果栈顶的top >= min 直接出，如果 top < min 则出现异常，将min作为pop的返回值，另外需要还原前一个最小值，方法是 min = 2 * min - top
其实这两种方法在思路上是完全一样的,只是学长提供的方法里,栈中所有元素都比我的方法里大v_push.不过,这种变化直接带来的好处是,在不更新最小值的情况下,压栈值和出栈值都不需要额外的计算,在高级语言层面上,一次加减法运算比单纯的赋值至少多了一次访存操作和一次alu的运算,这样估计来我的方法耗时会是学长方法的2倍左右,虽然时间复杂度都是一样的.
Stack<Integer> stack;
int min;
public MinStack() {
stack = new Stack<Integer>();
min = 0;
}
public void push(int number) {
if(stack.size() == 0) {
stack.push(number);
min = number;
} else{
if(number >= min) {
stack.push(number);
}else {
stack.push(2*number - min);
min = number;
}
}
}
public int pop() {
if(!stack.isEmpty()) {
int temp = stack.pop();
if(temp < min) {
int num = min;
min = 2*min - temp;
temp = num;
}
return temp;
}else {
return min;
}
}
public int min() {
return min;
}
Using only one stack - but still waste a lot of space
这种解法只用到了一个栈，还需要一个整型变量min_val来记录当前最小值，初始化为整型最小值，然后如果需要进栈的数字小于等于当前最小值min_val，那么将min_val压入栈，并且将min_val更新为当前数字。在出栈操作时，先将栈顶元素移出栈，再判断该元素是否和min_val相等，相等的话我们将min_val更新为新栈顶元素，再将新栈顶元素移出栈即可
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;
}
X.
private Stack<Integer> s1 = new Stack<>(); private Stack<Integer> s2 = new Stack<>(); /** initialize your data structure here. */ public MinStack() {} public void push(int x) { s1.push(x); if (s2.isEmpty() || s2.peek() >= x) s2.push(x); } public void pop() { // Cannot write like the following: // if (s2.peek() == s1.peek()) s2.pop(); // s1.pop(); int x = s1.pop(); if (s2.peek() == x) s2.pop(); } public int top() { return s1.peek(); } public int getMin() { return s2.peek(); }
需要注意的是上面的Java解法中的pop()中，为什么不能用注释掉那两行的写法，我之前也不太明白为啥不能对两个stack同时调用peek()函数来比较，如果是这种写法，那么不管s1和s2对栈顶元素是否相等，永远返回false。这是为什么呢，这我们就要到Java的对于peek的定义了，对于peek()函数的返回值并不是int类型，而是一个Object类型，这是一个基本的对象类型，如果我们直接用==来比较的话，那么肯定不会返回true，因为是两个不同的对象，所以我们一定要先将一个转为int型，然后再和另一个进行比较，这样才能得到我们想要的答案，这也是Java和C++的一个重要的不同点吧。
看到题目第一反应是用一个int minVal来记录整个stack当前的最小值就可以了。然后仔细想下，发现问题在于当这个最小值被pop以后，无法O(1)时间得到新的最小值。所以问题的关键在于要跟踪记录每个新数字压入栈时的当前最小值，而不是只记录一个总的最小值。
一种思路是将make_pair(xi, curMin)一起压入栈stack<pair<int,int>>中。但这种方法的空间复杂度为2n。再仔细观察，发现只有当push或pop的对象xi<= min(stack)时，才会影响到min(stack)的值。
用另一个stack<int> trackMin来记录min值的变化，trackMin.top()表示当前最小值。
当有新的xi<=trackMin.top()被压入时，将xi压入trackMin变为新的当前最小值。
当xi==trackMin.top()时被pop出时，trackMin也同时pop。
当有新的xi<=trackMin.top()被压入时，将xi压入trackMin变为新的当前最小值。
当xi==trackMin.top()时被pop出时，trackMin也同时pop。
这里的一个关键是理解为什么是x<=trackMin.top()而不是x<trackMin.top()。加入对于push(x)只有当x<trackMin.top()时，才将x压入trackMin中。
例如压入以下数后：
xi: 3 2 1 2 1
trackMin: 3 2 1
此时如果pop，则变为
xi: 3 2 1 2
trackMin: 3 2
然而实际栈里的最小值仍旧为1，这个1因为重复数字的关系在trackMin中丢失。
此时如果pop，则变为
xi: 3 2 1 2
trackMin: 3 2
然而实际栈里的最小值仍旧为1，这个1因为重复数字的关系在trackMin中丢失。
stack<int> s; stack<int> trackMin; public: void push(int x) { if(trackMin.empty() || x<=trackMin.top()) trackMin.push(x); s.push(x); } void pop() { if(s.empty()) return; if(s.top()==trackMin.top()) trackMin.pop(); s.pop(); } int top() { return s.top(); } int getMin() { return trackMin.top(); }
利用两个栈结构，其中一个是主要的正常stack，满足pop(), push()的O(1)时间要求，另外一个作为辅助的minStack，仅存入min的integer。 min = Integer.parseInt(minStack.peek().toString());
push()时，如果number >= min，则push到minStack上 pop()时，如果number == min，也从minStack上pop
题中的例子，最终stack为[2, 3, 1], minStack为 [2, 1]
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();
}
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MinStack() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int number) {
stack1.push(number);
if (!stack2.isEmpty()) {
stack2.push(Math.min(stack2.peek(), number));
} else {
stack2.push(number);
}
}
public int pop() {
if (stack1.isEmpty()) {
throw new NoSuchElementException();
}
stack2.pop();
return stack1.pop();
}
public int min() {
return stack2.peek();
}
X.
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;
}
}
}
https://simpleandstupid.com/2014/12/03/min-stack-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/
维护一个list就可以了，定义一个新的类StackNode，存当前的值和当前的最小值。
Minimum element in a stack - PrismoSkillsSolution is to have each stack node keep minimum of all nodes below it.
So during each insertion, minimum of new node is just the minimum of stack top and new node.
During deletion, minimum of stack is already there in the next top.
Similarly, a max can be kept in each node along with min to give max/min in O(1)
If the stack is very large, then the above approach may be wasting a lot of space.
A better approach may be to have a separate stack just to store the minimums.
This stack will store a decreasing order of nodes (from bottom to top) such that a new node will come on top
only when its smaller than the current minimum on this stack
When adding a new node to stack, this approach will store only the decreasing nodes and not the intermediate higher-valued nodes.
When deleting from the stack, new stack-top is compared with the min-stack's top.
If its larger than the min-stack's top, then the top of min-stack is also removed.
Read full article from Minimum element in a stack - PrismoSkills
维护一个list就可以了，定义一个新的类StackNode，存当前的值和当前的最小值。
class MinStack { StackNode stackHead = null; public void push(int x) { StackNode element = new StackNode(x); if(stackHead != null){ element.next = stackHead; element.min = Math.min(x, stackHead.min); stackHead = element; } else{ element.next = null; element.min = x; stackHead = element; } } public void pop() { if(stackHead != null) stackHead = stackHead.next; } public int top() { if(stackHead != null) return stackHead.val; else return 0; } public int getMin() { if(stackHead != null) return stackHead.min; else return 0; }}class StackNode { StackNode next; int val; int min; StackNode(int val) { next = null; this.val = val; min = 0; }}So during each insertion, minimum of new node is just the minimum of stack top and new node.
During deletion, minimum of stack is already there in the next top.
Similarly, a max can be kept in each node along with min to give max/min in O(1)
If the stack is very large, then the above approach may be wasting a lot of space.
A better approach may be to have a separate stack just to store the minimums.
This stack will store a decreasing order of nodes (from bottom to top) such that a new node will come on top
only when its smaller than the current minimum on this stack
When adding a new node to stack, this approach will store only the decreasing nodes and not the intermediate higher-valued nodes.
When deleting from the stack, new stack-top is compared with the min-stack's top.
If its larger than the min-stack's top, then the top of min-stack is also removed.
Read full article from Minimum element in a stack - PrismoSkills
