跟着姚桑学算法-包含min函数的栈

简介: 剑指offer算法

题. 包含min函数的栈

设计一个支持push,pop,top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

  • push(x)–将元素x插入栈中
  • pop()–移除栈顶元素
  • top()–得到栈顶元素
  • getMin()–得到栈中最小元素

数据范围
操作命令总数 [0,100]。

样例

MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin();   --> Returns -4.
minStack.pop();
minStack.top();      --> Returns 3.
minStack.getMin();   --> Returns -1.

【题解】-- 单调栈

除了维护基本的栈结构之外,还需要维护一个单调栈,来实现返回最小值的操作。
下面介绍如何维护单调栈:

  • 当我们向栈中压入一个数时,如果该数 ≤ 单调栈的栈顶元素,则将该数同时压入单调栈中;否则,不压入,这是由于栈具有先进后出性质,所以在该数被弹出之前,栈中一直存在一个数比该数小,所以该数一定不会被当做最小数输出。
  • 当我们从栈中弹出一个数时,如果该数等于单调栈的栈顶元素,则同时将单调栈的栈顶元素弹出。
  • 单调栈由于其具有单调性,所以它的栈顶元素,就是当前栈中的最小数。

复杂度分析:

四种操作都只有常数次入栈出栈操作,所以时间复杂度都是 O(1)。

C++代码实现:

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stackValue;
    stack<int> stackMin;
    MinStack() {

    }

    void push(int x) {
        stackValue.push(x);
        if (stackMin.empty() || stackMin.top() >= x)
            stackMin.push(x);
    }

    void pop() {
        if (stackMin.top() == stackValue.top()) stackMin.pop();
        stackValue.pop();
    }

    int top() {
        return stackValue.top();
    }

    int getMin() {
        return stackMin.top();
    }
};

/**
 * 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();
 */
目录
相关文章
|
2月前
|
算法 机器人 定位技术
【VRPTW】基于matlab秃鹰算法BES求解带时间窗的骑手外卖配送路径规划问题(目标函数:最优路径成本 含服务客户数量 服务时间 载量 路径长度)(Matlab代码实现)
【VRPTW】基于matlab秃鹰算法BES求解带时间窗的骑手外卖配送路径规划问题(目标函数:最优路径成本 含服务客户数量 服务时间 载量 路径长度)(Matlab代码实现)
|
19天前
|
机器学习/深度学习 传感器 算法
基于matlab瞬态三角哈里斯鹰算法TTHHO多无人机协同集群避障路径规划(目标函数:最低成本:路径、高度、威胁、转角)(Matlab代码实现)
基于matlab瞬态三角哈里斯鹰算法TTHHO多无人机协同集群避障路径规划(目标函数:最低成本:路径、高度、威胁、转角)(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 数据挖掘
【配送路径规划】基于螳螂虾算法MShOA求解带时间窗的骑手外卖配送路径规划问题(目标函数:最优路径成本 含服务客户数量 服务时间 载量 路径长度)研究(Matlab代码实现)
【配送路径规划】基于螳螂虾算法MShOA求解带时间窗的骑手外卖配送路径规划问题(目标函数:最优路径成本 含服务客户数量 服务时间 载量 路径长度)研究(Matlab代码实现)
|
2月前
|
算法 Python
【配送路径规划】基于遗传算法求解带时间窗的电动汽车配送路径规划(目标函数:最小成本;约束条件:续驶里程、额定载重量、数量、起始点)研究(Matlab代码实现)
【配送路径规划】基于遗传算法求解带时间窗的电动汽车配送路径规划(目标函数:最小成本;约束条件:续驶里程、额定载重量、数量、起始点)研究(Matlab代码实现)
|
11月前
|
搜索推荐 Python
利用Python内置函数实现的冒泡排序算法
在上述代码中,`bubble_sort` 函数接受一个列表 `arr` 作为输入。通过两层循环,外层循环控制排序的轮数,内层循环用于比较相邻的元素并进行交换。如果前一个元素大于后一个元素,就将它们交换位置。
248 67
|
10月前
|
算法
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
|
12月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
532 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
12月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
178 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
11月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
12月前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
257 3

热门文章

最新文章