P1-4 设计一个有getMin功能的栈

第一种设计方案

class getMinStack(object):
    def __init__(self):
        self.stackData = []
        self.stackMin = []

    def push(self, newNum):
        self.stackData.append(newNum)
        if not self.stackMin or newNum <= self.stackMin[-1]:
            self.stackMin.append(newNum)

    def pop(self):
        if len(self.stackData) == 0:
            raise Exception("栈为空")
        value = self.stackData.pop()
        if value == self.stackMin[-1]:
            self.stackMin.pop()
        return value

    def getMin(self):
        if len(self.stackMin) == 0:
            raise Exception("栈为空")
        else:
            return self.stackMin[-1]

s = getMinStack()
n = int(input())
for _ in range(n):
    command = input().split()
    if command[0] == 'push':
        s.push(int(command[1]))
    elif command[0] == 'pop':
        s.pop()
    elif command[0] == 'getMin':
        print(s.getMin())

. 运行时间 2415ms
. 占用内存 11612KB

第二种设计方案

class getMinStack(object):
    def __init__(self):
        self.stackData = []
        self.stackMin = []

    def push(self, newNum):
        self.stackData.append(newNum)
        if not self.stackMin or newNum <= self.stackMin[-1]:
            self.stackMin.append(newNum)
        else:
            self.stackMin.append(self.stackMin[-1])

    def pop(self):
        if len(self.stackData) == 0:
            raise Exception("栈为空")
        self.stackMin.pop()
        return self.stackData.pop()

    def getMin(self):
        if len(self.stackMin) == 0:
            raise Exception("栈为空")
        else:
            return self.stackMin[-1]

s = getMinStack()
n = int(input())
for _ in range(n):
    command = input().split()
    if command[0] == 'push':
        s.push(int(command[1]))
    elif command[0] == 'pop':
        s.pop()
    elif command[0] == 'getMin':
        print(s.getMin())

. 运行时间 2237ms
. 占用内存 10696KB

书上说
方案一 入栈时更省空间,出栈时更费时间;
方案二 入栈时更费空间,出栈时更省时间
可我感觉方案二 在运行时间和占用内存上都占优势 仅Python实现如此

排行榜上的优质答案:

import sys

num = int(sys.stdin.readline())  # 使用标准输入 仅读取一行(包括换行符)
stack = []
for i in range(num):
    op = sys.stdin.readline().split()
    if op[0] == 'push':
        stack.append(int(op[1]))
    if op[0] == 'pop':
        stack.pop()
    elif op[0] == 'getMin':
        print(min(stack))