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


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

相关文章
|
4月前
leetcode-155:最小栈
leetcode-155:最小栈
36 0
|
1月前
|
算法 C语言 C++
【practise】栈的压入和弹出序列
【practise】栈的压入和弹出序列
|
1月前
|
存储 算法
【算法】栈算法——最小栈
【算法】栈算法——最小栈
|
3月前
|
存储 人工智能 程序员
技术心得记录:堆(heap)与栈(stack)的区别
技术心得记录:堆(heap)与栈(stack)的区别
28 0
|
4月前
|
存储 Java 程序员
堆栈与堆(Stack vs Heap)有什么区别?
堆栈与堆(Stack vs Heap)有什么区别?
49 0
|
10月前
|
Python
配对堆(Pairing Heap
配对堆(Pairing Heap)是一种基于二叉堆的可并堆数据结构,它的主要特点是每个节点都有两个子节点,分别称为左子节点和右子节点。配对堆支持插入、查询最小值、合并和修改元素等操作。它具有速度快和结构简单的优势,但由于其为基于势能分析的均摊复杂度,无法可持久化。
101 0
|
11月前
|
存储 资源调度 调度
配对堆(Pairing heap
配对堆(Pairing heap)是一种优先队列的数据结构,它的主要特点是每个节点可以有一个优先级,元素的优先级可以是任意的,可以是整数、浮点数或其他类型。配对堆支持插入、删除最小元素(即弹出最小元素)、查找最小元素以及调整优先级等操作。它具有堆的性质,即任意节点的优先级大于等于(或小于等于)其子节点优先级。
95 0
|
11月前
|
存储
【Leetcode】155. 最小栈、JZ31 栈的压入、弹出序列
155. 最小栈 155. 最小栈 题目描述; 设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
37 0
|
算法 JavaScript 前端开发
日拱算法:用两个栈实现队列&包含min函数的栈
本篇带来【剑指offer】的两道初级算法题:冲~~