【力扣hot100】刷题笔记Day21

前言

快乐周日，做了个美梦睡了个懒觉，组会前刷刷栈的题吧

20. 有效的括号 - 力扣（LeetCode）

辅助栈

class Solution:def isValid(self, s: str) -> bool:dic = {')':'(',']':'[','}':'{'}st = []for c in s:if st and c in dic:if dic[c] == st[-1]:  st.pop()     # 和栈顶能匹配上就弹出else:return False # 匹配不上就返回Falseelse:st.append(c)return not st  # 空的话return True，不空有多余字符return False

155. 最小栈 - 力扣（LeetCode）

辅助栈

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:pop_x = self.stack.pop()if pop_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]

存元组

class MinStack:# 直接用一个栈存元组（栈顶，当前栈的最小值）def __init__(self):self.stack = []# 空直接存，非空就更新最小值def push(self, val: int) -> None:if not self.stack:self.stack.append((val,val))else:self.stack.append((val, min(val, self.stack[-1][1])))# 弹出元组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]

394. 字符串解码 - 力扣（LeetCode）

辅助栈

思路参考K神题解

class Solution:def decodeString(self, s: str) -> str:st, res, num =[], '', 0for c in s:if c.isdigit():num = num * 10 + int(c)  # 为了获得连续数字比如"100"→100elif c == '[':st.append((num, res))   # num表示倍数，res表示前缀res, num = '', 0        # 更新倍数和括号里的字符elif c == ']':now_num, now_res = st.pop()res = now_res + now_num * res  # 新前缀 = 旧前缀 + 倍数 × 括号里的字符else:res += c  # 括号里的字符增加 / 无括号则一直增加return res

递归法

class Solution:def decodeString(self, s: str) -> str:def dfs(s, i):res, num = '', 0while i < len(s):if s[i].isdigit():num = num * 10 + int(s[i])  # 为了获得连续数字比如"100"→100elif s[i] == '[':i, now_res = dfs(s, i+1)  # 从下一层中获取括号内的res和新的下标res += num * now_res      # 加入结果集num = 0                   # 更新倍数elif s[i] == ']':return i, res             # 将当前的坐标和结果返回上一层else:res += s[i]               # 更新总结果集/更新括号里的字符i += 1                        # 坐标到达最后退出循环return resreturn dfs(s, 0)

739. 每日温度 - 力扣（LeetCode）

单调栈

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)st = [0]            # 单调递减栈res = [0] * n     for i in range(n):# 如果栈顶有数且当前数大于栈顶，记录栈顶的结果，popwhile st and temperatures[i] > temperatures[st[-1]]:res[st[-1]] = i - st[-1]st.pop()# 栈为空 或 当前数小于等于栈顶，pushst.append(i)return res

84. 柱状图中最大的矩形 - 力扣（LeetCode）

前后缀dp

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:n = len(heights)left_i = [0] * n  # dp求左边第一个比当前小的数的下标right_i = [0] * n  # dp求右边第一个比当前小的数的下标left_i[0] = -1     # 初始化为-1right_i[n-1] = n   # 初始化为nfor i in range(1, n):  # 从前往后，如果前一个数不比当前小，则找前一个数的left_ilast = i - 1while last >= 0 and heights[last] >= heights[i]:last = left_i[last]left_i[i] = lastfor i in range(n-2, -1, -1):last = i + 1       # 从后往前，如果后一个数不比当前小，则找后一个数的right_iwhile last <= n - 1 and heights[last] >= heights[i]:last = right_i[last]right_i[i] = lastres = 0  # (当前值) * (右边第一小i - 左边第一小i - i)for i in range(n):res = max(res, heights[i] * (right_i[i] - left_i[i] - 1))return res

单调栈

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:stack = []  # 单调递增栈heights = [0] + heights + [0]  # 前后补0res = 0for i in range(len(heights)):while stack and heights[i] < heights[stack[-1]]:# stack[-1]是mid，i为右边第一个比它小的数，stack[-2]是左边第一个比它小的数mid = stack.pop()left = stack[-1]res = max(res, (i - left - 1) * heights[mid])stack.append(i)return res

42. 接雨水 - 力扣（LeetCode）

相向双指针
- 最简洁做法，在之前【力扣hot100】刷题笔记Day3-CSDN博客记录过了，本篇记录另外前后缀dp和单调栈的做法

前后缀dp

class Solution:def trap(self, height: List[int]) -> int:n = len(height)leftMax = [0] * n   # 左边最高柱（包括当前）leftMax[0] = height[0]  # 初始化为最左柱rightMax = [0] * n  # 右边最高柱（包括当前）rightMax[n-1] = height[-1]  # 初始化为最右柱for i in range(1, n):leftMax[i] = max(height[i], leftMax[i-1])for i in range(n-2, -1, -1):rightMax[i] = max(height[i], rightMax[i+1])res = 0for i in range(n):# 竖着算：每格雨水 = 左右最小的最高柱 - 当前高度res += min(leftMax[i], rightMax[i]) - height[i]return res

单调栈

class Solution:def trap(self, height: List[int]) -> int:st, res = [], 0   # 单调递减栈for i in range(len(height)):while st and height[i] >= height[st[-1]]:  # >=重复元素处理后替换栈顶mid = st.pop()  # 凹槽if not st:  # 特殊处理两个元素的情况breakleft = st[-1]  # st[-1]左边，i为右边h = min(height[i], height[left]) - height[mid]  # 雨水的高res += h * (i - left - 1)  # 横着算st.append(i)  # 栈为空或者满足递减值return res