为什么很多人失业，招人却越来越难？

继续今天的算法学习，学习几道栈相关的算法题。

• 1、LeetCode 20、有效的括号
• 2、LeetCode 1614、括号的最大嵌套深度
• 3、LeetCode 150、逆波兰表达式求值

一、LeetCode 20、有效的括号

题目描述

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

有效字符串需满足：

• 1、左括号必须用相同类型的右括号闭合。
• 2、左括号必须以正确的顺序闭合。

题目解析

有效的括号满足以下几个条件：

• 1、字符串的长度一定是偶数。
• 2、括号的匹配遵循右括号和最近的一个左括号进行匹配，它们匹配成功才有可能是有效的括号

在这个问题中，主要涉及到栈这一数据结构。栈是一种先进后出（LIFO）的数据结构，只允许在一端进行插入和删除操作。

算法考察点

1. 栈的应用：使用栈来处理括号匹配问题。
2. 字符串遍历：遍历字符串并进行判断。
3. 括号匹配：利用栈来验证括号的有效性。

算法思路

1. 初始化一个空栈。
2. 遍历字符串的每个字符：
   • 如果是左括号，则将其入栈。
   • 如果是右括号，则判断栈是否为空，为空则返回 False；不为空则将栈顶元素出栈并与当前右括号匹配，若不匹配则返回 False。
3. 遍历完字符串后，若栈为空，则括号匹配有效，返回 True；否则返回 False。

代码解析

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# // 有效的括号（ LeetCode 20 ）:https://leetcode-cn.com/problems/valid-parentheses
class Solution:
    def isValid(self, s: str) -> bool:
        # 当字符串长度为奇数的时候，属于无效情况，直接返回 False
        if len(s) % 2 == 1:
             # 无效情况，返回 False
             return False
        
       
        # 构建一个栈，用来存储括号
        stack = list()

        
        # 遍历字符串数组中的所有元素
        for c in s : 
            
            # 如果字符为左括号 ( ，那么就在栈中添加对左括号 （
            if c == '(' :
               
               # 添加对左括号 （
               stack.append('(')

             # 如果字符为左括号 [ ，那么就在栈中添加对左括号 [
            elif c == '[' :

               # 添加对应的右括号 ]
               stack.append('[')

             # 如果字符为左括号 { ，那么就在栈中添加对左括号 {
            elif c == '{' :

               # 添加对应的右括号 }
               stack.append('{')

               # 否则的话，说明此时 c 是 ）] } 这三种符号中的一种
            else :
               
               # 如果栈已经为空，而现在遍历的字符 c 是 ）] } 这三种符号中的一种
               # 找不到可以匹配的括号，返回 False
               # 比如这种情况  }{，直接从右括号开始，此时栈为空
               if not stack : 
                  return False
               
               # 如果栈不为空，获取栈顶元素
               top = stack[-1]

               # 将栈顶元素和此时的元素 c 进行比较，如果相同，则将栈顶元素移除
               if (top == '(' and c == ')' ) or (top == '[' and c == ']' ) or (top == '{' and c == '}')  :
                    # 移除栈顶元素
                    stack.pop()
               else :
                   # 如果不相同，说明不匹配，返回 False
                   return False

        
        # 遍历完整个字符数组，判断栈是否为空
        # 如果栈为空，说明字符数组中的所有括号都是闭合的
        # 如果栈不为空，说明有未闭合的括号
        return not stack

这段代码通过遍历字符串中的每个字符，并利用栈来验证括号的有效性。如果遇到左括号，则入栈；如果遇到右括号，则与栈顶元素匹配，若匹配则出栈，若不匹配则返回 False。遍历完字符串后，若栈为空，则括号匹配有效，返回 True；否则返回 False。

算法的优势

• 算法通过栈来实现括号的匹配验证，逻辑清晰，代码简洁。
• 时间复杂度为 O(n)，遍历一次字符串，空间复杂度为 O(n)，使用了额外的栈空间。

易错点

1. 在处理右括号时，需要判断栈是否为空，避免空栈出栈操作导致错误。
2. 在判断括号匹配时，需要注意栈顶元素与当前字符的匹配关系。

二、LeetCode 1614、括号的最大嵌套深度

题目描述

如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：

• 字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
• 字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
• 字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。

类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：

• depth("") = 0
• depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 "(" 或者 ")"
• depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
• depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串

例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。

给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。

示例 1：

输入：s = "(1+(2*3)+((8)/4))+1" 输出：3 解释：数字 8 在嵌套的 3 层括号中。

示例 2：

输入：s = "(1)+((2))+(((3)))" 输出：3

提示：

• 1 <= s.length <= 100
• s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
• 题目数据保证括号表达式 s 是 有效的括号表达式

题目解析

算法考察点

1. 栈的应用：使用栈来处理括号匹配问题。
2. 字符串遍历：遍历字符串并进行处理。
3. 括号匹配：利用栈来验证括号的有效性。

算法思路

1. 初始化两个变量 ans 和 size，分别表示最大嵌套深度和当前栈的大小，初始值均为 0。
2. 遍历字符串 s 中的每个字符：
   • 如果当前字符是左括号 '('，则将其入栈，同时更新栈的大小 size。
   • 如果当前字符是右括号 ')'，则将栈顶的左括号出栈，同时更新栈的大小 size。
3. 在遍历过程中，不断更新最大嵌套深度 ans，即取 ans 和 size 的较大值。
4. 遍历完成后，ans 即为所求的最大嵌套深度。

代码解析

class Solution:
    def maxDepth(self, s: str) -> int:

        # size 表示栈的大小
        # ans 表示 size 的最大值，也就是最终的结果值
        ans, size = 0, 0

        # 遍历字符串 s
        for ch in s:
            # 如果遇到了一个左括号，将其入栈
            if ch == '(':
                # 栈中元素的个数加 1
                size += 1
                # 更新深度的值
                ans = max(ans, size)
            # 如果遇到了一个右括号，弹出栈顶的左括号
            elif ch == ')':
                # 栈中元素的个数减 1
                size -= 1
        # 返回最大值
        return ans

这段代码通过遍历字符串 s 中的每个字符，并利用栈来验证括号的有效性。遍历过程中，通过记录栈的大小 size 并不断更新最大嵌套深度 ans，最终返回 ans 作为结果。

算法的优势

• 算法通过栈来实现括号的匹配验证，逻辑清晰，代码简洁。
• 时间复杂度为 O(n)，遍历一次字符串，空间复杂度为 O(1)，只使用了常量级的额外空间。

易错点

1. 在处理右括号时，需要确保栈中有左括号，避免空栈出栈操作导致错误。
2. 在更新最大嵌套深度时，需要取当前栈的大小和历史最大值的较大值。

三、LeetCode 150、逆波兰表达式求值

题目描述

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 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 <= 10^4
• tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

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

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

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

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + *也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

题目解析

算法考察点

1. 栈的应用：使用栈来实现逆波兰表达式的计算。
2. 字符串处理：对逆波兰表达式进行遍历和操作数的转换。
3. 运算符的处理：对运算符进行操作，并进行计算。

算法思路

1. 初始化一个空列表 result 作为栈，用于存储操作数。
2. 遍历逆波兰表达式中的每个元素 token
   • 如果 token 是运算符，则从栈中弹出两个操作数，进行相应的计算，并将结果压入栈中。
   • 如果 token 是操作数，则将其转换为整数，并压入栈中。
3. 遍历完整个表达式后，栈顶元素即为计算结果。

代码解析

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        result = []  # 初始化一个列表作为栈，存储操作数

        # 遍历字符串数组
        for token in tokens:
            if token in "+-*/":  # 如果是运算符
                rightNum = result.pop()  # 先出栈的是右操作数
                leftNum = result.pop()   # 后出栈的是左操作数
                # 根据运算符进行计算
                if token == "+":
                    ans = leftNum + rightNum
                elif token == "-":
                    ans = leftNum - rightNum
                elif token == "*":
                    ans = leftNum * rightNum
                elif token == "/":
                    ans = int(leftNum / rightNum)  # 注意整除
            else:
                ans = int(token)  # 如果是数字，转换为整数

            result.append(ans)  # 将计算结果压入栈中

        return result[-1]  # 返回栈顶元素

算法的优势

• 通过栈来实现逆波兰表达式的计算，逻辑清晰，代码简洁。
• 时间复杂度为 O(n)，遍历一次表达式，空间复杂度为 O(n)，使用了额外的栈空间。

易错点

1. 在处理除法运算时，需要注意整除和浮点数除法的区别，避免计算错误。
2. 在处理运算符时，需要确保栈中有足够的操作数，避免空栈出栈操作导致错误。