solution.md

# 最小栈

<p>设计一个支持 <code>push</code> ，<code>pop</code> ，<code>top</code> 操作，并能在常数时间内检索到最小元素的栈。</p>

<ul>
	<li><code>push(x)</code> &mdash;&mdash; 将元素 x 推入栈中。</li>
	<li><code>pop()</code>&nbsp;&mdash;&mdash; 删除栈顶的元素。</li>
	<li><code>top()</code>&nbsp;&mdash;&mdash; 获取栈顶元素。</li>
	<li><code>getMin()</code> &mdash;&mdash; 检索栈中的最小元素。</li>
</ul>

<p>&nbsp;</p>

<p><strong>示例:</strong></p>

<pre><strong>输入：</strong>
[&quot;MinStack&quot;,&quot;push&quot;,&quot;push&quot;,&quot;push&quot;,&quot;getMin&quot;,&quot;pop&quot;,&quot;top&quot;,&quot;getMin&quot;]
[[],[-2],[0],[-3],[],[],[],[]]

<strong>输出：</strong>
[null,null,null,null,-3,null,0,-2]

<strong>解释：</strong>
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --&gt; 返回 -3.
minStack.pop();
minStack.top();      --&gt; 返回 0.
minStack.getMin();   --&gt; 返回 -2.
</pre>

<p>&nbsp;</p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>pop</code>、<code>top</code> 和 <code>getMin</code> 操作总是在 <strong>非空栈</strong> 上调用。</li>
</ul>

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
/**
 * 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();
 */
```

## 答案

```cpp
其他三个都是错的
```
## 选项


### A

```cpp
class MinStack
{
public:
    /** initialize your data structure here. */
private:
    stack<long int> s; 
    stack<long int> mins;

public:
    MinStack()
    {
        while (!s.empty())
        {
            s.pop();
        }
        while (!mins.empty())
        {
            mins.pop();
        }
    }
    void push(int x)
    {
        if (s.empty())
        {
            s.push(x);
            mins.push(x);
        }
        else
        {
            if (mins.top() >= x)
            {
                s.push(x);
                mins.push(x);
            }
            else
            {
                mins.push(mins.top());
                s.push(x);
            }
        }
    }
    void pop()
    {
        s.pop();
        mins.pop();
    }

    int top()
    {
        return s.top();
    }
    int getMin()
    {
        return mins.top();
    }
};
```

### B

```cpp
class MinStack
{
public:
    /** initialize your data structure here. */
    stack<int> s;
    MinStack()
    {
    }

    void push(int x)
    {
        if (s.empty())
        {
            s.push(x);
            s.push(x);
        }
        else
        {
            int temp = s.top();
            s.push(x);
            if (x < temp)
            {
                s.push(x);
            }
            else
            {
                s.push(temp);
            }
        }
    }

    void pop()
    {
        s.pop();
        s.pop();
    }

    int top()
    {
        int temp = s.top();
        s.pop();
        int top = s.top();
        s.push(temp);
        return top;
    }

    int getMin()
    {
        return s.top();
    }
};
```

### C

```cpp
class MinStack
{
public:
    stack<int> s;
    stack<int> min;
    /** initialize your data structure here. */
    MinStack()
    {
    }

    void push(int x)
    {
        s.push(x);
        if (min.empty() || x <= min.top())
        {
            min.push(x);
        }
    }

    void pop()
    {
        if (s.top() == min.top())
            min.pop();
        s.pop();
    }

    int top()
    {
        return s.top();
    }
    int getMin()
    {
        return min.top();
    }
};
```