【Hot100刷题计划】Day04 栈专题 1~3天回顾（持续更新）

• LeetCode Hot 100 是最常被考察的题目集合，涵盖了面试中常见的算法和数据结构问题。
• 刷 Hot100可以让你在有限的时间内集中精力解决最常考的问题。
• 鼓励大家不仅要写出代码，最好理解问题的本质、优化解法和复杂度分析。
• 遇到问题要多交流多求问多分享，“多折腾”能加深印象。欢迎留言交流~

Day4 栈专题

4天为一个周期学习，3天刷题，1天回顾。今天就是第4天了，我们复习之前，带着刷下较简单的数据结构——栈。

20. 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

思路：

栈是先入后出，匹配括号也是找最后相对应的。只有3种括号，在看到左括号压栈的时候，直接使用待匹配的右括号。只需要找到后续与栈顶元素相同的右括号出栈。最后栈为空则有效。

class Solution:def isValid(self, s: str) -> bool:stack = []for i in s:if i == '(':stack.append(')')              # 将待匹配的括号分别压入栈elif i == '[':stack.append(']')elif i == '{':stack.append('}')elif not stack or i != stack[-1]:  # 如果还有括号未匹配，栈为空或者不匹配return Falseelse:stack.pop()                    # 匹配成功，栈顶元素出栈return True if not stack else False    # 栈为空，则有效；反之无效

155. 最小栈

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

实现 MinStack 类:

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

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

思路： 要快速找栈中的最小值。栈先进后出，可以在每个元素位置维护之前元素最小值，栈顶标记则为栈最小值。

class MinStack:def __init__(self):self.stack = [(0, inf)]  # 除了栈元素，还维护一个最小值def push(self, val: int) -> None:self.stack.append((val, min(self.stack[-1][1], val)))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]# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

思路： 栈匹配的问题，核心是遇到“ [ ”入栈，遇到“ ] ”出栈。记录下的res需要匹配数字，所以入栈需要记录下数字。还需要之前的字符串才能得到结果（相当于递归的更深一层返回值）。

class Solution:def decodeString(self, s: str) -> str:res = ""                    # 当前解码结果multi = 0                   # 当前数字stack = []                  # 栈，用于存储 [数字, 之前的解码结果]for char in s:if char.isdigit():                      # 如果是数字字符multi = multi * 10 + int(char)      # 计算数字elif char == '[':                       # 遇到 '['，将当前数字和解码结果入栈stack.append([multi, res])multi, res = 0, ""                  # 重置数字和解码结果elif char == ']':                       # 遇到 ']'，出栈并更新解码结果cur_multi, last_res = stack.pop()res = last_res + cur_multi * res    # 拼接字符串更新解码结果(从最后一个右括号开始，res开始找栈)else:                                   # 普通字符，直接拼接到解码结果res += charreturn res

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

思路： 使用一个栈记录目前待匹配元素，遍历数组，如果遇到大于栈顶元素的值就持续对比，更新ans.

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:stack = [0]                     # 使用单调栈记录未匹配找到更大值的元素ans = [0] * len(temperatures)   # 所有位置初始化为0for i in range(1, len(temperatures)):# 如果当前元素比栈顶元素要大，匹配到就更新ans，并弹出栈中已匹配元素，继续对比while stack and temperatures[i] > temperatures[stack[-1]]:ans[stack[-1]]  = i - stack[-1]stack.pop()# 所有元素都要入栈，往后匹配更大值stack.append(i)return ans