首页 hot100 栈
文章
取消

hot100 栈

发表于 2026/06/03 更新于 2026/06/04
作者 Tonite14
11 分钟阅读

打算在这系列博客把hot100的题扫一遍，分模块来。

有效的括号 题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

示例 5：

输入：s = “([)]”

输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

思路：

关键在于想到使用map，用map存储匹配关系，只要栈顶不匹配，就可以直接false了。当然，不用if也可以，但要使用三个if。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var isValid = function(s) {
    const stack = [];
    const map = { ')': '(', '}': '{', ']': '[' };

    for (const x of s) {
        if (x === '(' || x === '{' || x === '[') {
            stack.push(x); // 左括号入栈
        } else {
            if (stack.pop() !== map[x]) { // 不是左括号就是右括号，出栈和它匹配
            return false; // 匹配不上就false
        }
        }
    }
    return stack.length === 0; // 栈空了说明全匹配
};

全if，纯粹的括号匹配，不过因为每次都要判断六次，效率巨慢：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

var isValid = function(s) {
    const stack = [];

    for (const x of s) {
        if (x === '(') {
            stack.push(x);
        }
        else if (x === '{') {
            stack.push(x);
        }
        else if (x === '[') {
            stack.push(x);
        }
        else if (x === ')') {
            if (stack.pop() !== '(') return false;
        }
        else if (x === '}') {
            if (stack.pop() !== '{') return false;
        }
        else if (x === ']') {
            if (stack.pop() !== '[') return false;
        }
    }
    return stack.length === 0;
};

最小栈 题目描述：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

思路：

初始化堆栈对象，pushpoptop等操作都很简单，但是想在o(1)时间内检索到最小元素，只用一个栈实在是不太可能，对于栈来说，o(1)的操作只有push或者pop。所以getMin应该是和push或者pop有关。

可以考虑用两个栈，一个栈正常操作，另一个栈栈顶一直存储当栈顶元素为某值时，当前的最小值；只要两个栈同步操作，就能保证两个栈状态的一致性。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

var MinStack = function() {
    this.stack = [];
    this.minStack = [];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push(val);
    // 最小值栈：记录当前位置的最小值（当前值和之前最小值取较小者）
    if (this.minStack.length === 0) {
        this.minStack.push(val);
    } else {
        this.minStack.push(Math.min(val, this.minStack[this.minStack.length - 1]));
    }
};

MinStack.prototype.pop = function() {
    this.stack.pop();
    this.minStack.pop(); // 两个栈同步pop
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1]; // 栈顶就是当前最小值
};

如果不想每次都判空，可以在底部塞一个哨兵，虽然多占了一个空间，但是不会有影响：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var MinStack = function() {
    this.stack = [];
    this.minStack = [Infinity]; // 哨兵，永远比任何数大
};

MinStack.prototype.push = function(val) {
    this.stack.push(val);
    this.minStack.push(Math.min(val, this.minStack[this.minStack.length - 1]));
    // 不用判空，因为minStack至少有Infinity
};

MinStack.prototype.pop = function() {
    this.stack.pop();
    this.minStack.pop();
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1];
};

灵神的做法，非常简洁，但因为每次都要存入一个数组，数组是对象，比两个普通栈开销大，最后的效率会不如使用双栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class MinStack {
    constructor() {
        // 这里的 0 写成任意数都可以，反正用不到
        this.st = [[0, Infinity]]; // 栈底哨兵
    }

    push(val) {
        this.st.push([val, Math.min(this.getMin(), val)]);
    }

    pop() {
        this.st.pop();
    }

    top() {
        return this.st[this.st.length - 1][0];
    }

    getMin() {
        return this.st[this.st.length - 1][1];
    }
}

字符串解码 题目描述：

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 105。

示例 1：

1
2

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

1
2

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

1
2

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

1
2

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300]

思路：

有递归关系，有括号，当然考虑用栈，但是用栈的操作思路是不太好想的。实际上，在本道题中，与单调栈问题不同，我们只会一直入栈后一直出栈，入栈操作和出栈操作是互相匹配的，不会交叉。加上[]的外围内容已经被规定再左边，所以我们可以在入栈时对括号和外围信息进行统一处理。

本题也可以递归，但是递归不好想。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

var decodeString = function(s) {
    const stack = []; // 栈：保存遇到'['时的外层状态[str, num]
    let str = ""; // 当前正在拼接的字符串
    let num = 0; // 当前正在拼接的数字（重复次数）

    for (const ch of s) {
        if (ch >= '0' && ch <= '9') {
            // 数字：拼成完整的多位数，比如"12"先读1再读2
            num = num * 10 + parseInt(ch);
        } else if (ch === '[') {
            // 遇到左括号：暂停外层，保存当前str和num到栈中
            // 然后重置str和num，开始处理括号内的内容
            stack.push([str, num]);
            str = "";
            num = 0;
        } else if (ch === ']') {
            // 遇到右括号：内层处理完了，恢复外层状态
            // prevStr是括号前的字符串，repeat是重复次数
            // str是括号内的解码结果，重复repeat次拼到prevStr后面
            const [prevStr, repeat] = stack.pop();
            str = prevStr + str.repeat(repeat);
        } else {
            // 字母：直接拼到当前字符串
            str += ch;
        }
    }
    return str;
};

柱状图中最大的矩形 题目描述：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

img

1
2
3

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

img

1
2

输入： heights = [2,4]
输出： 4

提示：

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104

思路：

先放一下。

hot100
栈
本文由作者按照 CC BY 4.0 进行授权
最近更新
文章内容