1. 首页

LeetCode 155. 最小栈

题目地址()

题目描述

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

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
 

示例:

输入:
["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.
 

提示:

pop、top 和 getMin 操作总是在 非空栈 上调用。

难度:Middle

前置知识

公司

  • amazon
  • bloomberg
  • google
  • snapchat
  • uber
  • zenefits
  • 阿里
  • 腾讯
  • 百度
  • 字节

两个栈

思路

我们使用两个栈:

  • 一个栈存放全部的元素,push,pop都是正常操作这个正常栈。
  • 另一个存放最小栈。 每次push,如果比最小栈的栈顶还小,我们就push进最小栈,否则不操作
  • 每次pop的时候,我们都判断其是否和最小栈栈顶元素相同,如果相同,那么我们pop掉最小栈的栈顶元素即可

关键点

  • 往minstack中 push的判断条件。 应该是stack为空或者x小于等于minstack栈顶元素

代码

  • 语言支持:JS,C++,Java,Python

JavaScript Code:

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = []
    this.minStack = []
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x)
    if (this.minStack.length == 0 ||  x <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(x)
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    const x = this.stack.pop()
    if (x !== void 0 &&  x === this.minStack[this.minStack.length - 1]) {
        this.minStack.pop()
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
    return this.minStack[this.minStack.length - 1]
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

C++ Code:

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

    }

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

    }

    void pop() {
        int top = data.top();
        data.pop();
        if(top == helper.top())
        {
            helper.pop();
        }

    }

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

    int getMin() {
        return helper.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();
 */

Java Code:

public class MinStack {

    // 数据栈
    private Stack<Integer> data;
    // 辅助栈
    private Stack<Integer> helper;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        data = new Stack<>();
        helper = new Stack<>();
    }

    public void push(int x) {
        // 辅助栈在必要的时候才增加
        data.add(x);
        if (helper.isEmpty() || helper.peek() >= x) {
            helper.add(x);
        }
    }

    public void pop() {
        // 关键 3:data 一定得 pop()
        if (!data.isEmpty()) {
            // 注意:声明成 int 类型,这里完成了自动拆箱,从 Integer 转成了 int,
            // 因此下面的比较可以使用 "==" 运算符
            int top = data.pop();
            if(top == helper.peek()){
                helper.pop();
            }
        }
    }

    public int top() {
        if(!data.isEmpty()){
            return data.peek();
        }
    }

    public int getMin() {
        if(!helper.isEmpty()){
            return helper.peek();
        }
    }
}

Python3 Code:

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minstack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.minstack or x <= self.minstack[-1]:
            self.minstack.append(x)

    def pop(self) -> None:
        tmp = self.stack.pop()
        if tmp == self.minstack[-1]:
            self.minstack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def min(self) -> int:
        return self.minstack[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

复杂度分析
– 时间复杂度:O(1)
– 空间复杂度:O(1)

一个栈

思路

符合直觉的方法是,每次对栈进行修改操作(push和pop)的时候更新最小值。 然后getMin只需要返回我们计算的最小值即可,
top也是直接返回栈顶元素即可。 这种做法每次修改栈都需要更新最小值,因此时间复杂度是O(n).

LeetCode 155. 最小栈

是否有更高效的算法呢?答案是有的。

我们每次入栈的时候,保存的不再是真正的数字,而是它与当前最小值的差(当前元素没有入栈的时候的最小值)。
这样我们pop和top的时候拿到栈顶元素再加上上一个最小值即可。
另外我们在push和pop的时候去更新min,这样getMin的时候就简单了,直接返回min。

注意上面加粗的“上一个”,不是“当前的最小值”

经过上面的分析,问题的关键转化为“如何求得上一个最小值”,解决这个的关键点在于利用min。

pop或者top的时候:

  • 如果栈顶元素小于0,说明栈顶是当前最小的元素,它出栈会对min造成影响,我们需要去更新min。
    上一个最小的是“min – 栈顶元素”,我们需要将上一个最小值更新为当前的最小值

    因为栈顶元素入栈的时候的通过 栈顶元素 = 真实值 - 上一个最小的元素 得到的,
    而真实值 = min, 因此可以得出上一个最小的元素 = 真实值 -栈顶元素

  • 如果栈顶元素大于0,说明它对最小值没有影响,上一个最小值就是上上个最小值。

LeetCode 155. 最小栈
LeetCode 155. 最小栈

关键点

  • 最小栈存储的不应该是真实值,而是真实值和min的差值
  • top的时候涉及到对数据的还原,这里千万注意是上一个最小值

代码

  • 语言支持:JS,C++,Java,Python

Javascript Code:

/*
 * @lc app=leetcode id=155 lang=javascript
 *
 * [155] Min Stack
 */
/**
 * initialize your data structure here.
 */
var MinStack = function() {
  this.stack = [];
  this.minV = Number.MAX_VALUE;
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  // update 'min'
  const minV = this.minV;
  if (x < this.minV) {
    this.minV = x;
  }
  return this.stack.push(x - minV);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  const item = this.stack.pop();
  const minV = this.minV;

  if (item < 0) {
    this.minV = minV - item;
    return minV;
  }
  return item + minV;
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  const item = this.stack[this.stack.length - 1];
  const minV = this.minV;

  if (item < 0) {
    return minV;
  }
  return item + minV;
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
  return this.minV;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

C++ Code:

class MinStack {
    stack<long> data;
    long min = INT_MAX;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        data.push(x - min);
        if(x < min)
        {
            min = x;
        }

    }

    void pop() {
        long top = data.top();
        data.pop();
        // 更新最小值
        if(top < 0)
        {
            min -= top;
        }

    }

    int top() {
        long top = data.top();
        // 最小值为 min
        if (top < 0)
        {
            return min;
        }
        else{
            return min+top;
        }
    }

    int getMin() {
        return min;
    }
};

/**
 * 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();
 */

Java Code:

class MinStack {
    long min;
    Stack<Long> stack;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = x;
        }
        else {
            stack.push(x - min);
            if (x < min)
                min = x;
        }
    }

    public void pop() {
        long p = stack.pop();

        if (p < 0) {
            // if (p < 0), the popped value is the min
            // Recall p is added by this statement: stack.push(x - min);
            // So, p = x - old_min
            // old_min = x - p
            // again, if (p < 0), x is the min so:
            // old_min = min - p
            min = min - p;
        }
    }

    public int top() {
        long p = stack.peek();

        if (p < 0) {
            return (int) min;
        }
        else {
            // p = x - min
            // x = p + min
            return (int) (p + min);
        }
    }

    public int getMin() {
        return (int) min;
    }
}

Python Code:

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.minV = float('inf')
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x - self.minV)
        if x < self.minV:
            self.minV = x

    def pop(self) -> None:
        if not self.stack:
            return
        tmp = self.stack.pop()
        if tmp < 0:
            self.minV -= tmp

    def top(self) -> int:
        if not self.stack:
            return
        tmp = self.stack[-1]
        if tmp < 0:
            return self.minV
        else:
            return self.minV + tmp

    def min(self) -> int:
        return self.minV



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

复杂度分析
– 时间复杂度:O(1)
– 空间复杂度:O(1)

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 155. 最小栈

链接:https://www.javascriptc.com/4520.html

« 6React 的多态性
LeetCode 154. 寻找旋转排序数组中的最小值 II»
Flutter 中文教程资源

相关推荐

QR code