📚 plmblog

Appearance

11-栈

📅 发表于 2026/06/07
🔄 更新于 2026/08/05
👁️ — 次访问
📝 1838 字
⏳ 6 分钟

题目 ​

01-20-有效的括号 ​

01-20-有效的括号

leetcode-20

  • 输入：只含括号的字符串s。
  • 输出：判断s是否有效：左括号有右括号且按正确顺序 闭合。
  • ()[]{} --> True。(] --> False
括号

栈

DP

栈先进后出判断括号有效 ​

栈先进后出判断括号有效
  • 建立右左括号映射和栈。
  • 依次遍历字符串s
    • s为左括号：入栈
    • s为右括号：栈顶 出栈，是否为对应左括号？若不是，则不匹配。
  • 结束后若栈当为空，若仍有元素，说明不匹配。
python
def isValid(self, s: str) -> bool:
    # s为空或长度为奇数，直接返回False
    if not s or len(s) % 2 != 0:
        return False

    # 右左括号映射
    right2left = {"}": "{", ")": "(", "]": "["}

    # stack
    stack = []

    # 依次遍历每一个字符
    for ch in s:
        if ch in right2left:
            # 当前为右括号
            # 判断当前右括号对应的左括号 是否和栈顶元素相同
            top = stack.pop() if stack else "#"
            if top != right2left[ch]:
                return False
        else:
            # 当前为左括号，直接入栈
            stack.append(ch)  

    # 栈仍然有值，说明不匹配
    if stack:  
        return False
    return True

02-155-最小栈 ​

02-155-最小栈

leetcode-155

  • 实现MinStack，支持push、pop、top、get_min， 常数时间内检索到 最小元素。

  • 要求：O(1)时间 检索最小元素

数据栈和最小栈 ​

数据栈和最小栈
  • 两个栈
    • data_stack：正常存储入栈元素
    • min_stack：存储每一时刻最小值，栈顶为最小元素。长度和数据栈一致。
  • 入栈：当前最小值=min(当前值, 最小栈栈顶元素)。最小值入最小栈。数据栈正常入栈。
  • 出栈：数据栈和最小栈，同时出栈。
  • 访问最小元素：直接返回min_stack栈顶元素。
python
class MinStack:

  def __init__(self):
      self.data_stack = []
      self.min_stack = []

  def push(self, value: int) -> None:
      """ 入栈，数据栈和最小值栈长度相同
      """
      self.data_stack.append(value)

      # 计算当前时刻最小值，入最小栈
      current_min_value = value  
      if self.min_stack:
          current_min_value = min(self.min_stack[-1], value)
      # 当前时刻最小值，入最小栈
      self.min_stack.append(current_min_value)  


  def pop(self) -> None:
      if self.data_stack:
          # 两个栈长度相同，都做pop，保持一致
          self.data_stack.pop()
          self.min_stack.pop()

  def top(self) -> int:
      if self.data_stack:
          # 栈先进后出，直接利用-1取栈顶元素
          return self.data_stack[-1]  
      return None


  def getMin(self) -> int:
      if self.min_stack:
          # 由于存放的是每一时刻的最小值，直接取栈顶元素即可
          return self.min_stack[-1]  
      return None

03-394-字符串解码 ​

03-394-字符串解码

leetcode-394

  • 输入：编码过的字符串
  • 输出：解码后的字符串
  • 编码规则：k[encoded_string]，内部的字符串重复k次，k为正整数。
  • 示例：
    • 3[a] 2[bc] --> aaa bcbc
    • 3[a2[c]] --> acc acc acc

出栈字符4种可能性累加解码字符串 ​

出栈字符4种可能性累加解码字符串

  • 栈，当前层构建的字符串res，当前重复倍数multi

  • 依次遍历字符串

    • ch为数字：数字可能是多位数，需读多位做相加。

      • multi = multi * 10 + int(char)

    • ch为字母：当前层正在构建的字符串

      • res += ch

    • ch为左括号[：即将进入下一层嵌套

      • 当前[multi, res] 入栈，清空multi和res，准备计算括号内部的新数据

    • ch为右括号]：当前层计算结束，需和上一层合并

      • 从栈中弹出 last_multi，last_res

      • 当前res 重复last_multi次，并追加到last_res后面，作为新res

        new_res=last_res+last_multi×res

  • 遍历结束，返回res

python
def decodeString(self, s: str) -> str:
    """栈解码, multi, res,"""
    if not s:
        return ""

    # 当前层字符串
    res = ""
    # 当前层重复次数
    multi = 0

    # 栈，存储res-multi对
    stack = []

    for ch in s:
        if '0' <= ch <= '9':
            # ch为数字，计算multi
            # 有多位，需要计算倍数关系
            multi = multi*10 + int(ch) 
        elif ch == '[':
            # ch为左括号，存储当前res和multi，进入下一层计算
            stack.append((res, multi))  
            res, multi = "", 0
        elif ch == ']':
            # ch为右括号，当前层结束，弹出栈顶
            if stack:
                last_res, last_multi = stack.pop() 
                res = last_res + res * last_multi 
        else:
            # 普通字符，相加到当前res
            res += ch  
    # 遍历结束，返回res
    return res

04-739-每日温度 ​

04-739-每日温度

leetcode-739

  • 输入：temperatures数组，表示每日温度
  • 输出：answers数组，answers[i]，对第i天，下一个更高温度出现在几天后。
  • [30,40,50,60] --> [1, 1, 1, 0]；[73,74,75,71,69,72,76,73] --> [1,1,4,2,1,1,0,0]

单调递减栈计算温度天数 ​

单调递减栈
  • 构建stack，初始化全0 answers数组
  • 遍历每个日期-温度(i, temp)
    • 当栈不为空 + 当前温度>栈顶温度，执行循环
      • 表明：当前日期i温度 > 栈顶日期j温度，i是日期j的answer
      • 栈顶 温度日期j出栈
      • 利用当前日期计算栈顶日期：天数=answers[j]=i-j
    • 当前日期 入栈，存放索引而非温度。
    • 保证栈单调递减
python
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    """利用栈，计算每日温度的下一个最高温度在几天"""
    if not temperatures:
        return []

    n = len(temperatures)
    answers = [0] * n

    # 记录日期，先进后出；保持各日期单调递减
    stack = []

    # 遍历每一个日期
    for i, temp in enumerate(temperatures):
        while stack and temp > temperatures[stack[-1]]: 
            # 栈有元素，且当前日期温度>栈顶元素温度
            j = stack.pop()
            # i是第一个大于j温度的日期，对j来说，下一个最高温度在i-j天后
            answers[j] = i - j 
        # 当前日期入栈
        stack.append(i)

    return answers

05-84-柱状图中最大的矩形 ​

05-84-柱状图中最大的矩形

leetcode-84

  • 输入：heights数组，表示每个柱子的高度，宽度均为1
  • 输出：柱状图中，能勾勒出的最大矩形面积。
  • 示例
    • [2,1,5,6,2,3] --> 10
    • [2,4] --> 4，为2+2 或 单独4

哨兵单调递增栈左右边界计算矩形面积 ​

单调递增栈统计最大矩形

每个位置左右延伸计算面积

  • 位置i边界：左右延伸 left_i, right_i。延伸条件：≥height[i]
  • 位置i宽度：width = right_i - left_i + 1
  • 位置i面积：area = height[i] * width
  • 最终：选择最大位置面积

左右边界如何计算?

  • 使用单调栈+左右2边增加0哨兵，计算出栈元素左右边界，入栈出栈。
    • 单调栈：保证先入栈元素高度 < 后入栈元素高度，即相邻先入栈为后入栈的左边界。
  • 遍历每个位置(i, height)
    • 栈不为空 且 当前height < 栈顶元素高度 (当前为栈顶元素的右边界)
      • 当前栈顶元素mid 出栈：计算其左右边界和面积
      • mid 右边界：r=i
      • mid 左边界：访问目前栈顶元素，不出栈， l=stack[-1]
      • mid 面积：heights[mid] * (r-l-1)
    • 位置i 入栈

[2,1,5,6,2,3]示例

  • 2：只能延伸到自己，宽度=1，面积=2*1=2
  • 1：宽度=6，面积=1*6=6
  • 5：宽度=2，面积=5*2=10
  • 6：宽度=1，面积=6*1=6
  • 2：宽度=4，面积=2*4=8
  • 3：宽度=1，面积=3*1=3
python
def largestRectangleArea(self, heights: List[int]) -> int:
    """单调递增栈，左右边界，使用哨兵，处理边界问题，计算最大边界"""

    if not heights:
        return 0

    # 左右两边增加0哨兵，处理边界问题
    extended_heights = [0] + heights + [0] 

    stack = []
    max_area = 0

    # 依次遍历，每个高度
    for i, height in enumerate(extended_heights):

        while stack and extended_heights[stack[-1]] > height: 
            # 当前元素低于栈顶元素，则遇到block，栈顶出栈，计算mid的面积
            mid = stack.pop()

            # 左右边界 (l, r)
            r = i  
            l = stack[-1] 

            # 宽度，开区间，不包含l和r
            width = r - l - 1

            # 计算mid 扩展宽度的面积
            area = width * extended_heights[mid]
            # 更新最大面积
            max_area = max(area, max_area)
        stack.append(i)

    return max_area
总访客数：— · 总访问量：—
PLM's Blog @ 2016 - 2026