LeetCode 155. 最小栈

freesan44

发布于 2020-03-20 10:06:24

2530

发布于 2020-03-20 10:06:24

文章被收录于专栏：freesan44 freesan44freesan44

题目

设计一个支持 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.

解题思路

添加一个minIndex

class MinStack:

    def __init__(self):
        self.list = []
        self.minIndex = 0
        """
        initialize your data structure here.
        """


    def push(self, x: int) -> None:
        self.list.append(x)
        if len(self.list) > 0 and x < self.list[self.minIndex]:
            self.minIndex = self.list.index(x)
            # print("change: " + str(self.minIndex) + str(x))


    def pop(self) -> None:
        popNum = self.list.pop()
        if self.minIndex == (len(self.list)):
            # print("change: " + str(self.minIndex))
            self.minIndex = 0 if len(self.list) <=0 else self.list.index(min(self.list))
        return popNum


    def top(self) -> int:
        return None if len(self.list) <= 0 else self.list[-1]

    def getMin(self) -> int:
        # print("getMin: " + str(self.minIndex))
        return None if len(self.list) <= 0 else self.list[self.minIndex]

Github:https://github.com/freesan44/LeetCode

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法