> For the complete documentation index, see [llms.txt](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/stack-and-queue/zhan/min-stack.md).

# Min Stack

easy 原题链接：https\://leetcode.com/problems/min-stack/

## Min Stack

[原题链接](https://leetcode.com/problems/min-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.

### 例子

> Input \["MinStack","push","push","push","getMin","pop","top","getMin"] 
>
> \[\[],\[-2],\[0],\[-3],\[],\[],\[],\[]]
>
> Output \[null,null,null,null,-3,null,0,-2]
>
> Explanation MinStack 
>
> minStack = new MinStack(); 
>
> minStack.push(-2); 
>
> minStack.push(0); 
>
> minStack.push(-3); 
>
> minStack.getMin(); // return -3 
>
> minStack.pop();
>
> minStack.top(); // return 0 
>
> minStack.getMin(); // return -2

### 解法一

```cpp
class MinStack {
private:
    vector<int> stack;
public:
    /** initialize your data structure here. */
    void push(int x) {
        stack.push_back(x);
    }
    
    void pop() {
        stack.pop_back();
    }
    
    int top() {
        return stack[stack.size()-1];
    }
    
    int getMin() {
        int minV=INT_MAX;
        for(int i: stack){
            minV=min(minV,i);
        }
        return minV;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
```

### 解法二

[stack](http://cplusplus.com/reference/stack/stack/?kw=stack)

```cpp
class MinStack {
private:
    stack<int> s1;    
    stack<int> s2;   //for containing min value at top 
public:
    void push(int x) {
	    s1.push(x);
	    if(s2.empty() || x<=s2.top()) s2.push(x);	    
    }
    void pop() {
	    if(s1.top()==s2.top()) s2.pop();
	    s1.pop();
    }
    int top() {
	    return s1.top();
    }
    int getMin() {
	    return s2.top();
    }
};
```