剑指20-包含min函数的栈

Posted on | In |

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。

  • 两个元素一一对应的栈，在push和pop操作中同进同退：一个主栈，用来作为存储元素的栈；一个辅栈，用来存储最小元素，其每个元素表示主栈对应元素自身和之前元素里的最小值。
    • 计算栈中最小元素时，只要返回辅栈栈顶元素即可。
  • 辅栈的构建
    • 主栈push元素时，检查该元素与辅栈栈顶元素的大小关系，如果较小则也将该值push到辅栈，否则将辅栈栈顶元素复制一份push到辅栈。
    • 主栈pop元素时，辅栈也pop元素。
  • 思路与64-滑动窗口的最大值有异曲同工之妙。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def __init__(self):
        self.stack = []
        self.minstack = []
    def push(self, num):
        self.stack.append(num)
        if len(self.minstack) == 0:
            self.minstack.append(num)
        else:
            self.minstack.append(min(self.minstack[-1], num))
    def pop(self):
        self.minstack.pop(-1)
        return self.stack.pop(-1)
    def min(self):
        return self.minstack[-1]