LeetCode 155. Min Stack(Medium)#Stack

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.

ans1.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

class MinStack { stack<int> data; stack<int> helper; public: MinStack() { } void push(int val) { data.push(val); if(helper.empty() || helper.top() >= val) { helper.push(val); } } void pop() { int top = data.top(); data.pop(); if(top == helper.top()) { helper.pop(); } } int top() { return data.top(); } int getMin() { return helper.top(); } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */

Ref:

https://github.com/azl397985856/leetcode/blob/master/problems/155.min-stack.md

https://blog.csdn.net/myRealization/article/details/106953583

https://www.cnblogs.com/grandyang/p/4091064.html