https://leetcode.com/articles/max-stack/
https://blog.csdn.net/magicbean2/article/details/79327801
http://www.cnblogs.com/grandyang/p/7823424.html
http://www.cnblogs.com/grandyang/p/7823424.html
X. Double Linked List + TreeMap
https://zhuanlan.zhihu.com/p/46553913
http://www.cnblogs.com/grandyang/p/4091064.html
https://blog.csdn.net/magicbean2/article/details/79327801
http://www.cnblogs.com/grandyang/p/7823424.html
Design a max stack that supports push, pop, top, peekMax and popMax.
- push(x) -- Push element x onto stack.
- pop() -- Remove the element on top of the stack and return it.
- top() -- Get the element on the top.
- peekMax() -- Retrieve the maximum element in the stack.
- popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
Example 1:
MaxStack stack = new MaxStack(); stack.push(5); stack.push(1); stack.push(5); stack.top(); -> 5 stack.popMax(); -> 5 stack.top(); -> 1 stack.peekMax(); -> 5 stack.pop(); -> 1 stack.top(); -> 5
Note:
- -1e7 <= x <= 1e7
- Number of operations won't exceed 10000.
- The last four operations won't be called when stack is empty.
http://www.cnblogs.com/grandyang/p/7823424.html
这道题让我们实现一个最大栈，包含一般栈的功能，但是还新加了两个功能peekMax()和popMax()，随时随地可以查看和返回最大值。之前有一道很类似的题Min Stack，所以我们可以借鉴那道题的解法，使用两个栈来模拟，s1为普通的栈，用来保存所有的数字，而s2为最大栈，用来保存出现的最大的数字。
在push()函数中，我们先来看s2，如果s2为空，或者s2的栈顶元素小于等于x，将x压入s2中。因为s2保存的是目前为止最大的数字，所以一旦新数字大于等于栈顶元素，说明遇到更大的数字了，压入栈。然后将数组压入s1，s1保存所有的数字，所以都得压入栈。
在pop()函数中，当s2的栈顶元素和s1的栈顶元素相同时，我们要移除s2的栈顶元素，因为一个数字不在s1中了，就不能在s2中。然后取出s1的栈顶元素，并移除s1，返回即可。
在top()函数中，直接返回s1的top()函数即可。
在peekMax()函数中，直接返回s2的top()函数即可。
在popMax()函数中，先将s2的栈顶元素保存到一个变量mx中，然后我们要在s1中删除这个元素，由于栈无法直接定位元素，所以我们用一个临时栈t，将s1的出栈元素保存到临时栈t中，当s1的栈顶元素和s2的栈顶元素相同时退出while循环，此时我们在s1中找到了s2的栈顶元素，分别将s1和s2的栈顶元素移除，然后要做的是将临时栈t中的元素加回s1中，注意此时容易犯的一个错误是，没有同时更新s2，所以我们直接调用push()函数即可
A regular stack already supports the first 3 operations, so we focus on the last two.
For
peekMax, we remember the largest value we've seen on the side. For example if we add [2, 1, 5, 3, 9], we'll remember [2, 2, 5, 5, 9]. This works seamlessly with pop operations, and also it's easy to compute: it's just the maximum of the element we are adding and the previous maximum.
For
popMax, we know what the current maximum (peekMax) is. We can pop until we find that maximum, then push the popped elements back on the stack.
Our implementation in Python will showcase extending the
list class.- Time Complexity: for the
popMaxoperation, and for the other operations, where is the number of operations performed. - Space Complexity: , the maximum size of the stack.
class MaxStack {
Stack<Integer> stack;
Stack<Integer> maxStack;
public MaxStack() {
stack = new Stack();
maxStack = new Stack();
}
public void push(int x) {
int max = maxStack.isEmpty() ? x : maxStack.peek();
maxStack.push(max > x ? max : x);
stack.push(x);
}
public int pop() {
maxStack.pop();
return stack.pop();
}
public int top() {
return stack.peek();
}
public int peekMax() {
return maxStack.peek();
}
public int popMax() {
int max = peekMax();
Stack<Integer> buffer = new Stack();
while (top() != max)
buffer.push(pop());
pop();
while (!buffer.isEmpty())
push(buffer.pop());
return max;
}
}
https://zhuanlan.zhihu.com/p/46553913
下面这种解法没有利用一般的stack，而是建立一种较为复杂的数据结构，首先用一个list链表来保存所有的数字，然后建立一个数字和包含所有相同的数字的位置iterator的向量容器的映射map。
在push()函数中，把新数字加到list表头，然后把数字x的位置iterator加到数字映射的向量容器的末尾。
在pop()函数中，先得到表头数字，然后把该数字对应的iterator向量容器的末尾元素删掉，如果此时向量容器为空了，将这个映射直接删除，移除表头数字，返回该数字即可。
在top()函数中，直接返回表头数字即可。
在peekMax()函数中，因为map是按key值自动排序的，直接尾映射的key值即可。
在popMax()函数中，首先保存尾映射的key值，也就是最大值到变量x中，然后在其对应的向量容器的末尾取出其在list中的iterator。然后删除该向量容器的尾元素，如果此时向量容器为空了，将这个映射直接删除。根据之前取出的iterator，在list中删除对应的数字，返回x即可
Using structures like Array or Stack will never let us
popMax quickly. We turn our attention to tree and linked-list structures that have a lower time complexity for removal, with the aim of making popMax faster than time complexity.
Say we have a double linked list as our "stack". This reduces the problem to finding which node to remove, since we can remove nodes in time.
We can use a TreeMap mapping values to a list of nodes to answer this question. TreeMap can find the largest value, insert values, and delete values, all in time.
Let's store the stack as a double linked list
dll, and store a map from value to a List of Node.- When we
MaxStack.push(x), we add a node to ourdll, and add or update our entrymap.get(x).add(node). - When we
MaxStack.pop(), we find the valueval = dll.pop(), and remove the node from ourmap, deleting the entry if it was the last one. - When we
MaxStack.popMax(), we use themapto find the relevant node tounlink, and return it's value.
The above operations are more clear given that we have a working
DoubleLinkedList class. The implementation provided uses head and tail sentinels to simplify the relevant DoubleLinkedListoperations.
Time Complexity: for all operations except
peek which is , where is the number of operations performed. Most operations involving TreeMap are .
class MaxStack {
TreeMap<Integer, List<Node>> map;
DoubleLinkedList dll;
public MaxStack() {
map = new TreeMap();
dll = new DoubleLinkedList();
}
public void push(int x) {
Node node = dll.add(x);
if (!map.containsKey(x))
map.put(x, new ArrayList<Node>());
map.get(x).add(node);
}
public int pop() {
int val = dll.pop();
List<Node> L = map.get(val);
L.remove(L.size() - 1);
if (L.isEmpty())
map.remove(val);
return val;
}
public int top() {
return dll.peek();
}
public int peekMax() {
return map.lastKey();
}
public int popMax() {
int max = peekMax();
List<Node> L = map.get(max);
Node node = L.remove(L.size() - 1);
dll.unlink(node);
if (L.isEmpty())
map.remove(max);
return max;
}
}
class DoubleLinkedList {
Node head, tail;
public DoubleLinkedList() {
head = new Node(0);
tail = new Node(0);
head.next = tail;
tail.prev = head;
}
public Node add(int val) {
Node x = new Node(val);
x.next = tail;
x.prev = tail.prev;
tail.prev = tail.prev.next = x;
return x;
}
public int pop() {
return unlink(tail.prev).val;
}
public int peek() {
return tail.prev.val;
}
public Node unlink(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
return node;
}
}
class Node {
int val;
Node prev, next;
public Node(int v) {
val = v;
}
}
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.
public class MinStack { 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(); } }
这种解法只用到了一个栈，还需要一个整型变量min_val来记录当前最小值，初始化为整型最小值，然后如果需要进栈的数字小于等于当前最小值min_val，那么将min_val压入栈，并且将min_val更新为当前数字。在出栈操作时，先将栈顶元素移出栈，再判断该元素是否和min_val相等，相等的话我们将min_val更新为新栈顶元素，再将新栈顶元素移出栈即可
public class MinStack {
private int min_val = Integer.MAX_VALUE;
private Stack<Integer> s = new Stack<>();
/** initialize your data structure here. */
public MinStack() {}
public void push(int x) {
if (x <= min_val) {
s.push(min_val);
min_val = x;
}
s.push(x);
}
public void pop() {
if (s.pop() == min_val) min_val = s.pop();
}
public int top() {
return s.peek();
}
public int getMin() {
return min_val;
}
}
