📚 plmblog

Appearance

11-栈

📅 发表于 2026/06/07
🔄 更新于 2026/06/07
👁️ -- 次访问
📝 0 字
⏳ 0 分钟

题目 ​

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
python
def isValid(self, s: str) -> bool:
      """遍历每个字符，栈先进后出，左括号入栈，右括号判断栈顶元素"""
      if not s:
          return False

      # 括号元素map
      l2r = {
          "{": "}",
          "[": "]",
          "(": ")",
      }
      r2l = {v: k for k, v in l2r.items()}

      # 栈
      stack = []

      for ch in s:
          if ch in l2r.keys():
              # 左括号入栈
              stack.append(ch)
          else:
              # 右括号 判断栈顶元素是否相同
              if stack:
                  top_l = stack.pop()
                  if top_l != r2l[ch]:
                      # 栈顶左括号和当前右括号不同，返回False
                      return False
              else:
                  # 栈本无元素
                  return False
      if stack:
          # 栈仍然有元素，说明没有完全匹配
          return False
      else:
          return Truepython

02-155-最小栈 ​

02-155-最小栈

leetcode-155

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

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

数据栈和最小栈 ​

数据栈和最小栈
  • 两个栈
    • data_stack：正常存储栈元素
    • min_stack：存储每一时刻的最小值，保证栈顶为当前最小值。长度和data一致。
  • 入栈：当前最小值=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

栈解决字符串解码 ​

栈解决字符串解码

  • 栈，当前层构建的字符串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)
    • 当栈不为空 + 当前温度>栈顶温度，执行循环
      • 栈顶 温度日期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,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

单调递增栈循环

  • extended_heights：左右两边增加0哨兵，处理边界问题。
  • 遍历每个位置
  • 栈有值 + height[i] < 栈顶高度，执行循环
    • 栈顶 出栈，作为mid，计算mid左右扩展面积的柱子
    • i < mid，作为右边界；新栈顶元素j， j < mid，作为左边界
    • 宽度：不包含l和r，开区间。width = r-l-1
    • 计算mid面积： height[mid] * width
  • i入栈
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