【practise】最小栈

简介: 【practise】最小栈

关于我:



睡觉待开机:个人主页个人专栏: 《优选算法》《C语言》《CPP》生活的理想,就是为了理想的生活!作者留言

PDF版免费提供:倘若有需要,想拿我写的博客进行学习和交流,可以私信我将免费提供PDF版。

留下你的建议:倘若你发现本文中的内容和配图有任何错误或改进建议,请直接评论或者私信。

倡导提问与交流:关于本文任何不明之处,请及时评论和私信,看到即回复。



1.前言

最小栈,是栈相关练习题中的典型题目,这里来介绍一种简单解答方式。

2.题目简介

题目链接:LINK

题意比较简单,就是实现一种最小栈,这种栈可以实现O(1)时间复杂度内找到当前栈中最小的元素值是多少。

3.题解思路

我们在最小栈这个需要我们写的数据结构中内置两个栈。

第一个栈用于正常存储数据,用于支持正常的栈的push\pop\top等功能。

第二个栈我们用于记录最小值入栈的变化,如果入栈的值比当前最小值小/相等,那么最小栈也入一份同样的val值。

4.示例代码

class MinStack {
private:
stack<int> _st; //正常的栈
stack<int> _minst; //记录最小的值变化
public:
    MinStack() {
        //构造函数不用写,因为我们两个成员变量都是自定义类型,对于默认构造函数来说自定义类型会自动调用其构造函数。
    }
    
    void push(int val) {
        _st.push(val);
        if(_minst.empty() || _minst.top() >= val)
        {
            _minst.push(val);
        }
    }
    
    void pop() {
        int pop = _st.top();
        _st.pop();
        if(pop == _minst.top())
        {
            _minst.pop();
        }
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.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();
 */


好的,如果本篇文章对你有帮助,不妨点个赞~谢谢。

相关文章
|
8月前
leetcode-155:最小栈
leetcode-155:最小栈
44 0
最小栈 与 栈的压入、弹出序列
最小栈 与 栈的压入、弹出序列
51 0
最小栈 与 栈的压入、弹出序列
|
5月前
|
算法 C语言 C++
【practise】栈的压入和弹出序列
【practise】栈的压入和弹出序列
|
5月前
|
存储 算法
【算法】栈算法——最小栈
【算法】栈算法——最小栈
|
存储
【Leetcode】155. 最小栈、JZ31 栈的压入、弹出序列
155. 最小栈 155. 最小栈 题目描述; 设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
47 0
包含min函数的栈(其实就是实现一个最小栈)(简单难度)
包含min函数的栈(其实就是实现一个最小栈)(简单难度)
77 0
包含min函数的栈(其实就是实现一个最小栈)(简单难度)
|
算法
LeetCode-155. 最小栈(day35)
LeetCode-155. 最小栈(day35)
118 0
最小栈 Min_Stack
最小栈 Min_Stack
109 0
最小栈 Min_Stack
算法设计 --- 最小栈
算法设计 --- 最小栈