设计一个有getMin功能的栈

pexels-photo-3030365.jpeg

题目

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

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

示例：

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

思路

设计时使用两个栈
一个栈用来保存当前栈中的元素，记为stack_data
一个栈用于保存每一步的最小值，记为stack_min

方案一

新元素x入栈

1.数据x将要入栈，先入栈stack_data

2.判断栈stack_min是否为空，为空x直接入stack_min，否则判断stack_min栈顶元素和x的大小，如果x小于或者等于栈顶元素，则x入栈stack_min，大于则不做处理

3.获取栈的最小值则返回stack_min的栈顶元素

元素出栈

1.stack_data栈正常弹出栈顶元素y

2.判断stack_data弹出的元素y与stack_min栈顶元素的大小，如果y等于栈顶元素，则stack_min也弹出栈顶元素

方案二

新元素x入栈

1.数据x将要入栈，先入栈stack_data

2.判断栈stack_min是否为空，为空x直接入stack_min，否则判断stack_min栈顶元素和x的大小，如果x小于或者等于栈顶元素，则x入栈stack_min，大于的话则把stack_min的栈顶元素重复压入stack_min

元素出栈

1.stack_data栈正常弹出栈顶元素y

2.stack_min栈正常弹出栈顶元素z

3.获取栈的最小值则返回stack_min的栈顶元素

代码

方案一

class MinStack:

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

    def push(self, x: int) -> None:
        self.stack_data.append(x)
        if self.stack_min:
            if x <= self.stack_min[-1]:
                self.stack_min.append(x)
        else:
            self.stack_min.append(x)

    def pop(self) -> None:
        if self.stack_data and self.stack_min:
            if self.stack_min[-1] == self.stack_data.pop():
                self.stack_min.pop()

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

    def getMin(self) -> int:
        if self.stack_min:
            return self.stack_min[-1]

方案二

class MinStack:

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

    def push(self, x: int) -> None:
        self.stack_data.append(x)
        if self.stack_min:
            if x <= self.stack_min[-1]:
                self.stack_min.append(x)
            else:
                self.stack_min.append(self.stack_min[-1])
        else:
            self.stack_min.append(x)

    def pop(self) -> None:
        if self.stack_data and self.stack_min:
            self.stack_data.pop()
            self.stack_min.pop()

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

    def getMin(self) -> int:
        if self.stack_min:
            return self.stack_min[-1]

复杂度分析

方案一

• 时间复杂度：O(1)，“出栈”、“入栈”、“查看栈顶元素”的操作和数据量的多少无关，都是有限的步骤
• 空间复杂度：O(n)
• 方案一压入时稍省空间，弹出稍费时间

方案二

• 时间复杂度：O(1)，“出栈”、“入栈”、“查看栈顶元素”的操作和数据量的多少无关，都是有限的步骤
• 空间复杂度：O(n)
• 方案二压入时稍费空间，弹出稍省时间

---

公众号:《程序员养成记》

主要写算法、计算机基础之类的文章, 有兴趣来关注一起成长！

程序员养成记

版权声明 :著作权归作者所有，非商业转载请注明出处，禁止商业转载。