【力扣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 # 匹配不上就返回False
            else:
                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 =[], '', 0
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)  # 为了获得连续数字比如"100"→100
            elif 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 = '', 0
            while i < len(s):
                if s[i].isdigit():
                    num = num * 10 + int(s[i])  # 为了获得连续数字比如"100"→100
                elif 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 res
        return 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):
            # 如果栈顶有数且当前数大于栈顶，记录栈顶的结果，pop
            while st and temperatures[i] > temperatures[st[-1]]:
                res[st[-1]] = i - st[-1]
                st.pop()
            # 栈为空 或 当前数小于等于栈顶，push
            st.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     # 初始化为-1
        right_i[n-1] = n   # 初始化为n
        for i in range(1, n):  # 从前往后，如果前一个数不比当前小，则找前一个数的left_i
            last = i - 1
            while last >= 0 and heights[last] >= heights[i]:
                last = left_i[last]
            left_i[i] = last
        for i in range(n-2, -1, -1):
            last = i + 1       # 从后往前，如果后一个数不比当前小，则找后一个数的right_i
            while last <= n - 1 and heights[last] >= heights[i]:
                last = right_i[last]
            right_i[i] = last
        res = 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]  # 前后补0
        res = 0
        for 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 = 0
        for 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:  # 特殊处理两个元素的情况
                    break
                left = st[-1]  # st[-1]左边，i为右边
                h = min(height[i], height[left]) - height[mid]  # 雨水的高
                res += h * (i - left - 1)  # 横着算
            st.append(i)  # 栈为空或者满足递减值
        return res