大厂面试真题详解:带最小值操作的栈-阿里云开发者社区

开发者社区> 算法编程> 正文

大厂面试真题详解:带最小值操作的栈

简介: 大厂面试真题详解:带最小值操作的栈

实现一个栈, 支持以下操作:

  • push(val) 将 val 压入栈
  • pop() 将栈顶元素弹出, 并返回这个弹出的元素
  • min() 返回栈中元素的最小值
    要求 O(1) 开销.

在线评测地址:[领扣题库官网](https://www.lintcode.com/problem/min-stack/?utm_source=sc-tianchi-sz0929
)

样例:

输入: 
  push(1)
  min()
  push(2)
  min()
  push(3)
  min()
输出: 
  1
  1
  1

算法:最小栈

思路:

  • 要求O(1)时间内完成所有操作,压入栈弹和出栈顶元素并返回本来就是O(1)没有问题,要返回栈中元素最小值也是O(1)就需要一个辅助栈。
  • 在压入新元素时,如果辅助栈为空或者辅助栈顶元素大于新元素,那么新元素就是目前最小值,压入新元素;如果辅助栈顶元素小于新元素,那么再次压入栈顶元素。
  • 在弹出元素时,辅助栈跟着一起弹出栈顶元素。
  • 这样就满足了辅助栈内存储的最小值与存储数据的栈同步,查询最小值的操作是O(1)的。

复杂度:

  • 空间复杂度取决于输入的数据
  • 时间复杂度O(1)
public class MinStack {

    Stack<Integer> stack, minStack;

    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    public void push(int number) {
        stack.push(number);
        if (minStack.empty() || number < minStack.peek()) {
            minStack.push(number);
        } else {
            minStack.push(minStack.peek());
        }
    }

    /*
     * @return: An integer
     */
    public int pop() {
        minStack.pop();
        return stack.pop();
    }

    /*
     * @return: An integer
     */
    public int min() {
        return minStack.peek();
    }
}

更多题解参考:九章官网Solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接