Knowledge_Repository

主题

Teeker2026-04-06
829
3.1m

栈高频题型及解题模板（2023 年 10 月 01 日） ​

好的，这就为你整理一份栈高频题型清单，包含括号匹配、逆序处理、单调栈的常见变种和解题模板，你可以直接对照练习。

📚 栈高频题型清单 & 解题模板 ​

一、括号匹配类（必掌握） ​

1. 基础：有效括号 ​

题目：判断字符串中的括号是否合法匹配。

核心思路：左括号入栈，右括号出栈并检查匹配。

模板代码：

JavaScript

function isValidBracket(str) {
  const stack = [];
  const bracketMap = new Map([
    [')', '('],
    ['}', '{'],
    [']', '[']
  ]);
  for (const char of str) {
    if (bracketMap.has(char)) {
      // 右括号：检查栈顶是否匹配
      if (!stack.length || stack.pop() !== bracketMap.get(char)) return false;
    } else {
      // 左括号：入栈
      stack.push(char);
    }
  }
  return stack.length === 0;
}

2. 变种：删除无效括号 ​

题目：删除最少的括号，使剩下的字符串括号合法。

核心思路：用栈记录括号索引，标记需要删除的位置，最后拼接结果。

3. 变种：最长有效括号 ​

题目：找出字符串中最长的有效括号子串长度。

核心思路：栈底保存“最后一个无效括号的索引”，计算有效长度。

二、逆序处理类（基础高频） ​

1. 字符串/数组逆序 ​

题目：用栈实现字符串或数组的逆序输出。

模板代码：

JavaScript

function reverseByStack(s) {
  const stack = [];
  for (const char of s) stack.push(char);
  let res = '';
  while (stack.length) res += stack.pop();
  return res;
}

2. 变种：逆波兰表达式求值 ​

题目：计算逆波兰表达式（如 ["2","1","+","3","*"] → (2+1)*3=9）。

核心思路：数字入栈，遇到运算符弹出两个数字计算，结果再入栈。

三、单调栈类（面试高频） ​

1. 每日温度 ​

题目：找出每个温度下一个更高温度的天数。

模板代码：

JavaScript

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const res = new Array(n).fill(0);
  const stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && temperatures[i] > temperatures[stack.at(-1)]) {
      const prev = stack.pop();
      res[prev] = i - prev;
    }
    stack.push(i);
  }
  return res;
}

2. 下一个更大元素 I/II ​

题目：找每个元素在另一个数组/循环数组中的下一个更大元素。

核心思路：单调栈保存元素索引，遍历数组时记录每个元素的下一个更大值。

3. 柱状图中最大的矩形 ​

题目：计算柱状图中能勾勒出的最大矩形面积。

核心思路：维护单调递增栈，找到每个柱子左右第一个更小的柱子，计算宽度。

4. 接雨水 ​

题目：计算柱子能接住的雨水量。

核心思路：维护单调递减栈，遇到更高柱子时计算凹槽面积。

💡 栈题型通用解题思路 ​

  1. 括号匹配：左括号入栈，右括号出栈校验，栈空则合法。

  2. 逆序处理：利用栈“后进先出”特性，入栈再出栈即可实现逆序。

  3. 单调栈：维护栈内元素单调性（递增/递减），一次遍历找到“下一个更大/更小元素”，时间复杂度 O(n)。

如果你需要，我可以把这些高频题目的完整可运行代码整理成一个文件，你直接复制就能跑，方便在机考或面试中快速套用。需要我帮你整理吗？

（注：文档部分内容可能由 AI 生成）

最近更新