LeetCode 716. Max Stack

 716. Max Stack

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

• MaxStack() Initializes the stack object.
• void push(int x) Pushes element x onto the stack.
• int pop() Removes the element on top of the stack and returns it.
• int top() Gets the element on the top of the stack without removing it.
• int peekMax() Retrieves the maximum element in the stack without removing it.
• int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

 

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

 

Constraints:

• -107 <= x <= 107
• At most 104 calls will be made to push, pop, top, peekMax, and popMax.
• There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

 

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call? 

	class MaxStack {
	public:
	// 構造体
	struct Node {
	int val;
	Node* next;
	Node* prev;
	Node(int x) {
	this->val = x;
	this->next = NULL;
	this->prev = NULL;
	}
	};
	Node* tail;
	map<int, stack<Node*>> hash;
	MaxStack() {
	tail = nullptr;
	}
	void push(int x) {
	Node* n = new Node(x);
	if(!tail) tail = n;
	else {
	tail->next = n;
	n->prev = tail;
	tail = n;
	}
	hash[x].push(n);
	}
	int pop() {
	int t = this->top();
	if(tail->prev){
	tail->prev->next = nullptr;
	tail = tail->prev;
	} else
	tail = nullptr;
	hash[t].pop();
	if(hash[t].empty()) hash.erase(t);
	return t;
	}
	int top() {
	return tail->val;
	}
	int peekMax() {
	return hash.rbegin()->first;
	}
	int popMax() {
	int t = this->peekMax();
	Node* n = hash[t].top();
	if(tail->val == t){
	this->pop();
	} else {
	// remove from hash
	hash[t].pop();
	if(hash[t].empty()) hash.erase(t);
	// remove from list
	if(n->prev)
	n->prev->next = n->next;
	if(n->next)
	n->next->prev = n->prev;
	}
	return t;
	}
	};
	/**
	* Your MaxStack object will be instantiated and called as such:
	* MaxStack* obj = new MaxStack();
	* obj->push(x);
	* int param_2 = obj->pop();
	* int param_3 = obj->top();
	* int param_4 = obj->peekMax();
	* int param_5 = obj->popMax();
	*/

view raw 716. Max Stack.cpp hosted with ❤ by GitHub