###### tags: `Leetcode` `easy` `design` `python` `c++`

# 155. Min Stack

## [題目出處:] https://leetcode.com/problems/min-stack/

## 題目:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

* MinStack() initializes the stack object.
* void push(int val) pushes the element val onto the stack.
* void pop() removes the element on the top of the stack.
* int top() gets the top element of the stack.
* int getMin() retrieves the minimum element in the stack.
You must implement a solution with **O(1) time complexity for each function**.

## 解題想法:
關鍵!! 額外創個minstack將最小值存入

## Python:

class MinStack(object):

    def __init__(self):
        self.stack = []
        #getMin取最小值用ㄉ
        self.minstack = [float('Inf')]

    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        #值放在stack最後
        self.stack.append(val)
        #若值小於等於minstack的最後一筆data 則加入minstack
        if val <= self.minstack[-1]:
            self.minstack.append(val)
        
    def pop(self):
        """
        :rtype: None
        """
        #從 stack 移除最上面一筆值，如果該值等於 min_stack 最後一筆，一併從堆疊移除
        if self.stack[-1] == self.minstack[-1]:
            self.minstack.pop()
        self.stack.pop()
        

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]
        

    def getMin(self):
        """
        :rtype: int
        """
        return self.minstack[-1]
        
if __name__ == '__main__':
    obj = MinStack()
    obj.push(-2)
    obj.push(0)
    obj.push(-3)
    obj.getMin()
    obj.pop()
    param_3 = obj.top()
    param_4 = obj.getMin()
    print(param_3,param_4)

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

## C++:

#include<iostream>
#include<stack>
using namespace std;
class MinStack {
public:
    MinStack() {
        //init no need to write
    }

    void push(int val) {
        cur_stack.push(val);
        if (min_stack.empty() || val<=min_stack.top())
            min_stack.push(val);
    }

    void pop() {
        if (cur_stack.top()==min_stack.top())
            min_stack.pop();
        cur_stack.pop();
    }

    int top() {
        return cur_stack.top();
    }

    int getMin() {
        return min_stack.top();
    }
private:
    stack<int> cur_stack;
    stack<int> min_stack;
};

int main(){
    MinStack *res=new MinStack();
    res->push(-2);
    res->push(0);
    res->push(-3);
    int min_val=res->getMin();
    cout<<min_val<<endl;
    res->pop();
    int top_val=res->top();
    cout<<top_val<<endl;
    int min2_val=res->getMin();
    cout<<min2_val<<endl;
    return 0;
}