leetcode刷题记录——栈

20 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

1 <= s.length <= 104

s 仅由括号 '()[]{}' 组成

思路

这道题基本上都多多少少做过、听过，思路基本上就是一个，遇到括号左边压入栈，遇到括号右边就匹配，成功就弹出栈顶失败就false

代码

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dic = {'(':')', '[':']', '{':'}'}
        for i in s:
            if i in dic:
                stack.append(i)
            elif len(stack) == 0 or dic[stack.pop()] != i:
                return False
        return len(stack) == 0

时间复杂度

时间复杂度O(n)，执行时间43ms，消耗内存16.5MB

71 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，’...‘）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能 以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.‘ 或 ‘..‘）。
返回简化后得到的 规范路径 。

示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。 

示例 2：

输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

输入：path = "/a/./b/../../c/"
输出："/c"

提示：

1 <= path.length <= 3000

path 由英文字母，数字，'.'，'/' 或 '_' 组成。

path 是一个有效的 Unix 风格绝对路径。

思路

首先将所有的/给去掉，然后在我们没遇到' ', '.', '..'时就会直接压入当前元素，然后当我们遇到'..'就直接将栈顶元素弹出，因为要返回上一级。最后用/连接每个字符并在最前面添加一个/

代码

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for i in path.split('/'):
            if i == '..' and stack:
                stack.pop()
            elif i not in ['', '.', '..']:
                stack.append(i)
        return '/' + '/'.join(stack)

时间复杂度

时间复杂度O(n)，执行时间49ms，消耗内存16.3MB

155 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：

["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：

[null,null,null,null,-3,null,0,-2] 

解释：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-231 <= val <= 231 - 1

pop、top 和 getMin 操作总是在 非空栈 上调用

push, pop, top, and getMin最多被调用 3 * 104 次

思路

这里基本上都是采用辅助栈的形式去做，做法其实大差不差

四个函数分别说一下

push，每当我们push一个新值进来，如果小于等于辅助栈的栈顶则一起push到辅助栈，也就更新了最小值

pop，如果栈顶和辅助栈的栈顶一样，两个都pop，保证最小值在辅助栈中

top，返回主栈栈顶元素

getMin，返回辅助栈栈顶元素也即最小值

代码

class MinStack:
    # 初始化两个栈，一个用于存储所有元素，另一个用于存储最小元素
    def __init__(self):
        self.stack = []
        self.min_stack = []

    # 向栈中添加元素，并更新最小元素栈
    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    # 从栈中移除元素，并更新最小元素栈
    def pop(self) -> None:
        x = self.stack.pop()
        if x == self.min_stack[-1]:
            self.min_stack.pop()

    # 获取栈顶元素
    def top(self) -> int:
        return self.stack[-1]

    # 获取栈中的最小元素
    def getMin(self) -> int:
        return self.min_stack[-1]

时间复杂度

时间复杂度O(1)，执行时间59ms，消耗内存20MB

这里容易有一个误区就是pop的时候我们把辅助栈的最小元素给pop了，那么我们是不是就没有辅助栈了呢。并不是，辅助栈也是会被更新的，如果我们在pop的下一个就需要运行getMin了，那得到的就肯定为空了。当我们在后续还有新的push，那必然获得的就不是这个为空的了。

150 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。

每个操作数（运算对象）都可以是一个整数或者另一个表达式。

两个整数之间的除法总是 向零截断 。

表达式中不含除零运算。

输入是一个根据逆波兰表示法表示的算术表达式。

答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：

((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

1 <= tokens.length <= 104

tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

思路

首先第一个需要理解的点是逆波兰表达式是一个后缀表达式，所以我们可以先将后缀表达式转换为逆波兰表达式，并计算结果。而我们常用的计算式是中缀表达式，所以明白了这点就可以大概构思出怎么做。

接下来我们需要想到几个问题。

第一当用例中出现负数怎么办，负数我们可以直接转换为- + num这样就变相的改成了计算式，然后数字直接int为整数就行。

第二，当我们看到题目中的第三条时会有一个很无语的事情，就是除法需要 向零截断，而python的除余结果是直接向下取整。然而，在我们第一步的操作后，我们直接解决了这个问题，唯一需要注意的是我们除式的结果需要转化为int型变量

代码

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        dic = {'+':lambda x,y:x+y, '-':lambda x,y:x-y, '*':lambda x,y:x*y, '/':lambda x,y:int(x/y)}
        # 定义一个字典dic，存储运算符和对应的lambda函数，用于执行相应的算术操作
        for token in tokens:
            # 遍历tokens列表中的每一个token
            if token in dic:
                # 如果token是运算符
                y = stack.pop()
                x = stack.pop()
                # 从stack中弹出两个操作数
                stack.append(dic[token](x,y))
                # 执行相应的算术操作，并将结果压入stack
            else:
                # 如果token是操作数
                stack.append(int(token))
                # 将token转换为整数并压入stack
        return stack[0]
        # 返回stack中唯一的元素，即逆波兰表达式的计算结果

时间复杂度

时间复杂度O(n)，执行时间40ms，消耗内存18.2MB

224 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

1 <= s.length <= 3 * 105

s 由数字、'+'、'-'、'('、')'、和 ' ' 组成

s 表示一个有效的表达式

'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)

'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)

输入中不存在两个连续的操作符

每个数字和运行的计算将适合于一个有符号的 32位 整数

思路

这个问题的核心是如何处理加减法运算，并正确处理括号内的优先级。我们可以通过以下步骤来解决问题：

1. 符号转换：我们将 + 用 1 表示，将 - 用 -1 表示。这样，当遇到加减号时，可以通过将当前数字乘以符号值来简化运算过程。

2. 处理括号：当遇到左括号 ( 时，需要将当前的计算结果和运算符号压入栈中，保存当前的运算状态。这是因为括号内的运算结果会影响括号外的结果。遇到右括号 ) 时，需要弹出栈顶的运算符号和结果，并将括号内的计算结果与之相结合。

示例
例如对于表达式 (1+(4+5+2)-3)+(6+8)，我们首先处理最内层的括号，然后逐步将结果合并到外层的运算中。

代码

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        sign = 1  # 1表示加号，-1表示减号
        result = 0
        
        for char in s:
            if char.isdigit():
                num = num * 10 + int(char)
            elif char == '+':
                result += sign * num
                num = 0
                sign = 1
            elif char == '-':
                result += sign * num
                num = 0
                sign = -1
            elif char == '(':
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = 1
            elif char == ')':
                result += sign * num
                num = 0
                result *= stack.pop()  # 乘以括号前的符号
                result += stack.pop()  # 加上括号前的结果
        
        # 处理最后一个数字
        result += sign * num
        
        return result

时间复杂度

时间复杂度：O(n)，执行时间57ms，消耗内存16.9MB