专栏首页CtrlCV博客【剑指Offer】包含min函数的栈

【剑指Offer】包含min函数的栈

题目

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); –> 返回 -3. minStack.pop(); minStack.top(); –> 返回 0. minStack.min(); –> 返回 -2.

提示:

各函数的调用总次数不超过 20000 次

题解

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指Offer】表示数值的字符串

    请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”、”5e2”、”-123”、”3.1416”、”0123”都表示数值,但”1...

    小新哟
  • 【剑指Offer】顺时针打印矩阵

    输入:matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出:[1,2,3,6,9,8,7,4,5] 示例 2:

    小新哟
  • 【剑指Offer】I. 从上到下打印二叉树

    小新哟
  • 【iPhone10周年】王威廉谈NLP:智能助理几家仍需努力

    【新智元导读】什么是自然语言处理?在 iPhone十周年之际,王威廉应 UC Santa Barbara Current 之邀请,谈了谈人工智能,并简要介绍了自...

    新智元
  • html 学习(css class选择器)

    文/某个胖子(简书作者) 原文链接:http://www.jianshu.com/p/802afaab545b 著作权归作者所有,转载请联系作者获得授权,并...

    bear_fish
  • VIPKID估值超过30亿美金?创始人身价暴涨,腾讯成为大赢家

    熟悉在线英语教育的朋友,一定听说过VIPKID这个平台。根据媒体的报道,VIPKID目前已经是全球最大的少儿英语在线教育平台之一。从去年8月到今年7月,不到一年...

    光荣与梦想1987
  • 第十五天、杨辉三角

    题目 输出杨辉三角 1、程序分析     利用杨辉三角形的特性,进行求解。 2、程序实现 /***************************...

    Jack_Cui
  • MCU上的代码执行时间

    在许多实时应用程序中,二八原则并不生效,CPU 可以花费95%(或更多)的时间在不到5% 的代码上。电动机控制、引擎控制、无线通信以及其他许多对时间敏感的应用程...

    半吊子全栈工匠
  • Working with Errors in Go 1.13

    Damien Neil and Jonathan Amsterdam 17 October 2019

    陌无崖
  • Linux平台 Oracle 12cR2 RAC安装Part2

    本文安装环境:RHEL 6.5 + Oracle 12.2.0.1 GI & RAC

    Alfred Zhao

扫码关注云+社区

领取腾讯云代金券