📖 栈与滑动窗口专题怎么用？
栈处理"配对/嵌套"，滑动窗口处理"子串/子数组"。两道经典题代表了两种核心思想。
本专题包含 2 道题，都是外企面试高频真题。每道题按统一结构讲解：
- 题目描述 — 用人话翻译，不用读三遍才懂
- 生活类比 — 把抽象问题变成熟悉的生活场景
- 暴力思路 → 优化思路 — 面试官想看到的思考过程
- IDE 代码 — 带注释的 JS 实现 + 行号
- 复杂度分析 — 时间/空间，面试必问
- 面试加分项 — 能说出来的额外思考
复习建议：先看生活类比理解问题本质，再看思路建立解题框架，最后手写代码 3 遍形成肌肉记忆。面试时先口述思路，确认无误后再写代码。
1有效括号 (Valid Parentheses) Easy
题目（人话版）
判断一个括号字符串是否合法。合法 = 每个左括号都有对应的右括号，且顺序正确。
"()[]{}" → ✅ 合法"([)]" → ❌ 不合法（先开的 `[` 还没关，就先关了 `(`）"{[]}" → ✅ 合法（最里层的 `[]` 先关，再关外层 `{}`）
💡 生活类比：括号匹配就像叠盘子——你先放一个大盘子（`{`），再放一个中盘子（`[``），最后放一个小盘子（`(`）。拿盘子的时候必须从上往下拿：先拿小盘子（`)`），再拿中盘子（`]`），最后拿大盘子（`}`）。这就是"后进先出"——栈（Stack）！
思路：栈
遇到左括号
→
压入栈
遇到右括号
→
看栈顶是否匹配
→
匹配则弹出
/
不匹配则返回 false
栈的变化：左括号入栈，遇到右括号检查栈顶是否匹配
validBrackets.js
function isValid(s) {
const stack = [];
const map = { ')': '(', ']': '[', '}': '{' };
for (const char of s) {
if (char === '(' || char === '[' || char === '{') {
// 左括号：压入栈
stack.push(char);
} else {
// 右括号：看栈顶是不是对应的左括号
if (stack.pop() !== map[char]) {
return false;
}
}
}
return stack.length === 0; // 栈空了 = 全部匹配完
}
关键细节：循环结束后一定要检查 stack.length === 0！如果输入是 "(("，循环结束时栈里还剩两个左括号没被匹配，也是不合法的。
时间 O(n)，空间 O(n)。这道题的核心就一句话：遇到左括号入栈，遇到右括号出栈检查。
2最长不重复子串 (Longest Substring) Medium
题目（人话版）
找一个字符串里最长的"不重复子串"的长度。比如 "abcabcbb"，最长的不重复子串是 "abc"（长度 3），再往后就遇到重复的 a 了。
💡 生活类比：想象你在逛超市拿免费试吃——每种小吃只能拿一次。你依次拿了 A、B、C，正准备拿第四种 D，发现 D 和之前拿过的 A 是同一种！怎么办？把 A 之前的都丢掉（包括 A），然后继续从当前位置往后拿。整个过程里，你手里最多同时拿了几种？那就是答案。
思路：滑动窗口 + Set
"滑动窗口"就是两个指针 left 和 right 组成一个窗口，窗口里是不重复的字符。right 不断往右扩大窗口，遇到重复字符时 left 往右缩小窗口。
滑动窗口：right 扩大遇到重复时，left 跳过重复元素
longestSubstring.js
function lengthOfLongestSubstring(s) {
const set = new Set(); // 窗口里的字符集合
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
// 如果右边碰到重复字符，左边一直缩，直到不重复
while (set.has(s[right])) {
set.delete(s[left]);
left++;
}
set.add(s[right]); // 把当前字符加入窗口
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
时间 O(n)，空间 O(min(n, 26)) = O(1)（字符集有限，最多 26 个字母）。
滑动窗口模板：这类题有个固定套路——right 在 for 循环里一直走，遇到条件不满足时用 while 让 left 追赶。记住这个模板，很多"子串/子数组"题都能套。
📋 栈与滑动窗口专题速查表
| # | 题目 | 难度 |
|---|
| 1 | 有效括号 (Valid Parentheses) | Easy |
| 2 | 最长不重复子串 (Longest Substring) | Medium |
考点核心：栈与滑动窗口专题的核心就是"用对工具，降复杂度"。
面试时拿到题先想："这道题能用栈与滑动窗口吗？"
如果能，先说思路再写代码，面试官就知道你的分析能力。
🔗 其他考点专题
→ 双指针专题：回文检测 (Valid Palindrome), 反转字符串 (Reverse String), 合并两个有序数组 (Merge Sorted Arrays), 移动零 (Move Zeroes)
→ 哈希表专题：两数之和 (Two Sum), 有效的字母异位词 (Valid Anagram), 数组去重/判断有重复 (Contains Duplicate), 第一个唯一字符 (First Unique Character)
→ 动态规划专题：斐波那契数列 (Fibonacci), 爬楼梯 (Climbing Stairs), 最大子序和 (Max Subarray)
→ 位运算专题：只出现一次的数字 (Single Number), 缺失数字 (Missing Number)
→ 综合技巧专题：FizzBuzz, 买卖股票的最佳时机 (Best Time to Buy/Sell Stock), 多数元素 (Majority Element), 旋转数组 (Rotate Array), 二分查找 (Binary Search)
← 返回图解算法与模式