【剑指offer】包含min函数的栈，C++实现

骑猪看日落 2021-12-17 13:49 72阅读 0赞

[博客文章索引地址][Link 1]

[博客文章中代码的github地址][github]

#### **1.题目** ####

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中调用push、pop、top、min的时间复杂度都是o(1)。

#### **2.思路** ####

定义一个辅助栈，用于存放数据栈每次入栈时的最小元素，辅助栈的栈顶元素是数据栈内最小值。

**举例：**创建一个空数据栈和空辅助栈。

1.数据栈中压入3，辅助栈为空栈，最小值为3，辅助栈压入3

2.数据栈中压入4，4大于辅助栈的栈顶元素3，最小值为3，辅助栈压入3

3.数据栈中压入2，2小于辅助栈的栈顶元素3，最小值为2，辅助栈压入2

4.数据栈中压入1，1小于辅助栈的栈顶元素2，最小值为1，辅助栈压入1

5.数据栈弹出栈顶元素，辅助栈弹出栈顶元素，辅助栈弹出栈顶元素后的栈顶元素是当前数据栈的最小值

6.数据栈弹出栈顶元素，辅助栈弹出栈顶元素，辅助栈弹出栈顶元素后的栈顶元素是当前数据栈的最小值

**注意：数据栈和辅助栈操作同步，即对数据栈插入时，同时辅助栈也插入；弹出数据栈栈顶元素时，同时弹出辅助栈栈顶元素。**

[![image][]][image 1]

[![image][image 2]][image_image 2]

#### **3.代码** ####

**[牛客网][Link 2]**

class Solution {
    public:
        void push(int value) 
        {
            data.push(value);
           
            if(data.empty() || value<smin.top())
                smin.push(value);
            else
                smin.push(smin.top());
        }
        
        void pop() 
        {
            if(!data.empty() && !smin.empty())
            {
                data.pop();
                smin.pop();
            }
        }
        
        int top() 
        {
            return data.top();
        }
        
        int min() 
        {
            return smin.top();
        }
    private:
        stack<int> data;
        stack<int> smin;
    };

#### 4.测试用例 ####

*  压入栈的数字比最小数字大
 *  压入栈的数字比最小数字小
 *  弹出栈的数字是最小数字
 *  弹出栈的数字不是最小数字

转载于:https://www.cnblogs.com/wanglei5205/p/8622442.html

[Link 1]: http://www.cnblogs.com/wanglei5205/p/8495773.html
[github]: http://github.com/wanglei5205
[image]: /images/20211217/e909c381db56442bbd19158314d339b1.png
[image 1]: https://images2018.cnblogs.com/blog/1307402/201803/1307402-20180322111910823-1892708770.png
[image 2]: https://images2018.cnblogs.com/blog/1307402/201803/1307402-20180322111912613-1386478460.png
[image_image 2]: /images/20211217/d7b5a79c436b42bcb5a1facc4ba7c6dc.png
[Link 2]: https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=11173&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking