专栏首页Jack-Cui155.Min Stack(Stack-Easy)

155.Min Stack(Stack-Easy)

    Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); –> Returns -3. minStack.pop(); minStack.top(); –> Returns 0. minStack.getMin(); –> Returns -2.

题目: 设计一个支持push、pop、top和能返回最小值stack中最小值的stack

思路: 创建两个stack,一个保存所有元素,一个负责保存最小元素。保存最小元素的top元素即为所有元素的最小元素。看代码,很容易理解。

Language : cpp

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> all_stk;
    stack<int> min_stk;

    void push(int x) {
        all_stk.push(x);
        if(min_stk.empty() || min_stk.top() >= x){
            min_stk.push(x);
        }
    }
    void pop() {
        if(all_stk.top() == min_stk.top()){
            min_stk.pop();
        }
        all_stk.pop();
    }

    int top() {
        if(all_stk.empty()){
            return 0;
        }
        else{
            return all_stk.top();
        }
    }

    int getMin() {
        if(min_stk.empty()){
            return 0;
        }
        else{
            return min_stk.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();
 */

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 225. Implement Stack using Queues(Stack-Easy)

    Implement the following operations of a stack using queues. push(x) – Push eleme...

    Jack_Cui
  • 150.Evaluate Reverse Polish Notation(Stack-Medium)

    Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid...

    Jack_Cui
  • Day9、Python

    题目回数是指从左向右读和从右向左读都是一样的数,例如123321,909。请利用filter()滤掉非回数。 1、程序分析     filter()把传...

    Jack_Cui
  • c++ 哈夫曼树简便构造(数据结构作业篇)

        MinHeapNode(char data, unsigned freq)

    星辉
  • leetcode378. Kth Smallest Element in a Sorted Matrix

    在一个从左到右,从上到下均有序的二维数组中,找到从小到第k个数字,这里需要注意,不要求一定要是唯一的值,即假设存在这样一个序列1,2,2,3,则第三个数字是2而...

    眯眯眼的猫头鹰
  • (重点)链式栈

    顺序栈的实现在于使用了数组这个基本数据结构,数组中的元素在内存中的存储位置是连续的,且编译器要求我们在编译期就要确定数组的大小,这样对内存的使用效率并不高,一来...

    猿人谷
  • 怎么样将小程序代码上传到腾讯云服务器

    怎么样将小程序代码上传到腾讯云服务器,小程序代码上传到腾讯云服务器?微信小程序因为其不占内存、用完即走的便捷性,在日常生活中越来越流行,而且功能强大,在性...

    企业上云的意义
  • 马克贝尼奥夫在达沃斯上对第四次工业革命影响的发言

    W. Lee Howell: 欢迎大家,前面还有一些空坐大家往前坐在我们开始这场会议之前我们讨论的是关于第四次工业革命的影响,我们有非常优秀的一组讨论嘉宾来谈这...

    臭豆腐
  • 张小龙首次全面阐述小程序,定档1月9日上线(内附视频+全文)

    各位朋友,大家早上好!我是张小龙。 非常感谢大家一大早来到广州参加微信公开课。去年公开课是我第一次露面,并且在去年差不多这个时候时候宣布了我们的小程序要启动并且...

    腾讯大讲堂
  • 这里有一个成为我们合作伙伴的机会!

    腾讯云商标域名合作伙伴招募会来了! 我们欢迎广大有实力、有想法的同行人 成为我们的合作伙伴 与我们一起开启企业服务新版图 扫描下方海报二维码即可报名 我们期待...

    腾讯云DNSPod团队

扫码关注云+社区

领取腾讯云代金券