当前位置: 首页 > article >正文

C++ 最小栈 - 力扣(LeetCode)

点击链接即可查看题目:155. 最小栈 - 力扣(LeetCode)

一、题目 

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

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

  • -231 <= val <= 231 - 1
  • poptop 和 getMin 操作总是在 非空栈 上调用
  • pushpoptop, and getMin最多被调用 3 * 104 次

二、解题思路以及代码

* 1. 利用两个栈,一个为正常栈(保存所有的进出栈数据),一个为最小栈(只有当数据为最小时,才会入栈)

* 2. 核心在于:入栈时,若数据最小,需要两个栈都要入栈,出栈时,如果出的数据为最小,需要更新最小栈 

class MinStack {
public:
    MinStack() 
    {}
    void push(int val) 
    {
        st.push(val);
        if(minst.empty() || val < minst.top().val )
        {
            conut_data c_val;
            c_val.count = 1;
            c_val.val = val;
            minst.push(c_val);
        }
        else if(minst.top().val == val)
        {
            ++minst.top().count;
        }
    }

    void pop() 
    {
        if(st.top() == minst.top().val)
        {
            if(minst.top().count == 1)
            {
                minst.pop();
            }
            else
            {
                --minst.top().count;
            }
        }
        st.pop();
    }

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

    int getMin() 
    {
        return minst.top().val;
    }

    struct conut_data
    {
        int count;
        int val;
    };

    stack<int> st;
    stack<conut_data> minst;
};

http://www.kler.cn/a/454379.html

相关文章:

  • 杂项记录一些笔记
  • linux服务器上CentOS的yum和Ubuntu包管理工具apt区别与使用实战
  • AIOps平台的功能对比:如何选择适合的解决方案?
  • 简单贪吃蛇小游戏的设计与实现
  • es创建的索引状态一直是red
  • Effective C++ 条款 09:绝不在构造和析构过程中调用 virtual 函数
  • python操作Elasticsearch执行增删改查
  • 十二月第23讲:.NET 9 New features-AOT相关的改进
  • ubuntu搭建redis cluster集群三主三从(从0搭建,小白也会,不啰嗦)
  • (十)Ubuntu 20.04+akiaaa大神 Stable Diffusion整合包 AI绘画教程-外挂VAE模型等快捷设置教程
  • HarmonyOS NEXT 实战之元服务:静态案例效果---电动车电池健康状况
  • DPO(Direct Preference Optimization)算法解释:中英双语
  • 嵌入式学习-QT-Day11
  • .NET Core 中使用 C# 获取Windows 和 Linux 环境兼容路径合并
  • springcloud依赖
  • MongoDB 创建用户、User、Role 相关 操作
  • 机器学习基础算法 (二)-逻辑回归
  • 【LeetCode 面试经典150题】详细题解之哈希表篇
  • QT-【常用容器类】-QList类 QLinkedList类
  • stp生成树协议