设计getMin功能的栈

[编程题]设计getMin功能的栈

热度指数：15577 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

每次输入 [1,*] 时，表示向栈中加入数字 * ，[2] 表示移除栈顶元素，[3] 表示输入栈中最小元素，添加最小元素到结果集中即可。

数据范围：操作数 $0 \le n \le 1000000$

要求：各操作的时间复杂度 $O(1)$ ，空间复杂度 $O(n)$

示例1

输入

[[1,3],[1,2],[1,1],[3],[2],[3]]

输出

[1,2]

说明

 操作分别是：向栈push3，向栈push2，向栈push1，此时从栈底到栈顶是[3,2,1]。获得最小值，此时是1。栈pop操作，此时栈底到栈顶是[3,2]。获得最小值，此时是2。

备注:

有三种操作种类，op1表示push，op2表示pop，op3表示getMin。你需要返回和op3出现次数一样多的数组，表示每次getMin的答案

1<=操作总数<=1000000
-1000000<=每个操作数<=1000000
数据保证没有不合法的操作

算法知识视频讲解

Python

wengJJ

Python

@DaDaTheNoob的答案非常nice,这里做下笔记

堆记录数字与最小值的偏移量

data:[3,1,4,4,-1,6]

offset:[3,-2,3,3,-2,8]

可以发现offset小于0，则证明该数影响了最小值，所以pop的时候只需要检查offfset值即可

当pop出的元素是影响最小值的元素时，此时只需要利用offset修正最小值即可

#
# return a array which include all ans for op3
# @param op int整型二维数组 operator
# @return int整型一维数组
#
class Solution:
    def getMinStack(self , op ):
        # write code here
        stack = []
        result = []
        min_num = None
        offset = 0
        for i in op:
            if i[0]==1:
                if not stack:
                    min_num=i[1]
                offset = i[1]-min_num
                stack.append(offset)
                if i[1]<min_num:
                    min_num = i[1]
            elif i[0]==2:
                offset_num = stack.pop()
#                 如果偏移量小于0，证明min_num受该数影响
                if offset_num<0:
                    min_num = min_num - offset_num
            elif i[0]==3:
                result.append(min_num)
        return result

发表于 2021-04-19 18:30:05 回复(0)

Python

8浅笑8

python用正常栈和最小栈，结果通过率75超时。。。

#
# return a array which include all ans for op3
# @param op int整型二维数组 operator
# @return int整型一维数组
#
class Solution:
    st = []
    m = []
    def push1(self, num):
        self.st.append(num)
        if len(self.m) <= 0&nbs***bsp;num <= self.m[-1]:
            self.m.append(num)
    def pop1(self):
        if len(self.st) <= 0:
            return None
        r = self.st.pop()
        if r == self.m[-1]:
            self.m.pop()
        return r
    def getMin1(self):
        if len(self.m) <= 0:
            return None
        else:
            return self.m[-1]
    def getMinStack(self , op ):
        res = []
        for item in op:
            if item[0] == 1:
                self.push1(item[1])
            elif item[0] == 2:
                self.pop1()
            elif item[0] == 3:
                res.append(self.getMin1())
            else:
                return None
        return res
        # write code here

发表于 2020-09-18 14:45:07 回复(0)