栈的基础概念与经典题目（Leetcode题解-Python语言）

本文主要是介绍栈的基础概念与经典题目（Leetcode题解-Python语言），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

栈是先入后出（后入先出）的数据结构，常用操作就 push 和 pop，Python中用列表实现即可，基本概念可以看Leetbook相关章节。

155. 最小栈（剑指 Offer 30. 包含min函数的栈）

class MinStack:
    def __init__(self):
        self.stack = [(0, float('+inf'))]

    def push(self, x: int) -> None:
        self.stack.append((x, min(self.stack[-1][1], x)))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

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

实现最小栈的关键就是要用辅助栈记录每次 push 操作时的最小值，这样栈值在递增时，最小值永远是第一个值（如 [1, 2, 3, 4] 对应 [1, 1, 1, 1]）；在递减时，最小值永远是当前值（如 [4, 3, 2, 1] 对应 [4, 3, 2, 1]）。

20. 有效的括号

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for char in s:
            if char == '(' or char == '[' or char == '{':
                stack.append(char)
            else:
                if stack == []:
                    return False
                else:
                    pre = stack.pop()
                    if (char == ')' and pre != '(') or (char == ']' and pre != '[') or (char == '}' and pre != '{'):
                        return False
        return True if stack == [] else False

分类讨论：如果是三个左括号之一，就 push 进入栈；如果是三个右括号之一，就检查栈顶，若栈顶为空就肯定不匹配，不为空则考察弹出的栈顶元素，若不是对应的左括号则返回 False。最后如果还有左括号（栈非空），也返回 False。

946. 验证栈序列（剑指 Offer 31. 栈的压入、弹出序列）

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        pop_pointer = 0
        stack = []
        for num in pushed:
            stack.append(num)
            while stack and pop_pointer < len(popped) and stack[-1] == popped[pop_pointer]:
                stack.pop()
                pop_pointer += 1
        return pop_pointer == len(popped)

用指针记录 popped 序列，然后逐个把 pushed 序列的元素 push 进入栈中，如果出现相同值，则弹出栈顶元素，同时指针右移1位，如果所有元素都能pop 则返回 True。

739. 每日温度

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        length = len(temperatures)
        ans = [0] * length
        stack = []
        for i in range(length):
            temperature = temperatures[i]
            # 如果第i天的温度大于前面某天的温度
            while stack and temperature > temperatures[stack[-1]]:
                prev_index = stack.pop()  # 前面某天的下标
                ans[prev_index] = i - prev_index # ans中前面某天的答案即天数
            # 记录第i天的温度
            stack.append(i)
        return ans

遍历每一天的温度，用一个栈记录每天的温度下标，当遍历到第 i 天时，比较第 i 天是否大于前面某天的温度，如果是则弹出该天（已找到答案），并在 ans 数组中记录下天数（差值）。

这篇关于栈的基础概念与经典题目（Leetcode题解-Python语言）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！