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

2021/12/6 12:16:35

本文主要是介绍栈的基础概念与经典题目(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语言)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程