文章

hot100栈题解

发表于 更新于
作者 匆匆那年 29 分钟阅读

20. 有效的括号

问题描述

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

有效字符串需满足：

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

示例 1：

输入：s = “()”

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

提示：

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

题解

以下是关于 LeetCode 第 20 题“有效的括号”的 C++ 解法：

解题思路

  1. 使用栈（std::stack）来辅助判断括号匹配。
  2. 遍历字符串：
    • 如果遇到左括号（'(', '{', '['），将其压入栈中。
    • 如果遇到右括号（ ')', '}', ']'），检查栈是否为空：
      • 如果栈为空，说明没有匹配的左括号，返回 false。
      • 如果栈不为空，取出栈顶的左括号，检查是否匹配：
        • 若匹配，则继续。
        • 若不匹配，返回 false。
  3. 遍历结束后，检查栈是否为空：
    • 如果栈为空，说明所有括号都匹配，返回 true。
    • 如果栈不为空，说明有未闭合的左括号，返回 false。

代码实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <stack>
#include <unordered_map>

bool isValid(std::string s) {
    std::stack<char> stack;
    std::unordered_map<char, char> matching = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };

    for (char c : s) {
        // 如果是右括号
        if (matching.count(c)) {
            // 栈为空或栈顶不匹配，返回 false
            if (stack.empty() || stack.top() != matching[c]) {
                return false;
            }
            // 匹配则弹出栈顶
            stack.pop();
        } else {
            // 左括号入栈
            stack.push(c);
        }
    }

    // 栈为空说明完全匹配
    return stack.empty();
}

int main() {
    std::string s1 = "()";
    std::string s2 = "()[]{}";
    std::string s3 = "(]";
    std::string s4 = "([])";

    std::cout << std::boolalpha;
    std::cout << "Example 1: " << isValid(s1) << std::endl;
    std::cout << "Example 2: " << isValid(s2) << std::endl;
    std::cout << "Example 3: " << isValid(s3) << std::endl;
    std::cout << "Example 4: " << isValid(s4) << std::endl;

    return 0;
}

代码解释

  1. 使用 std::unordered_map 存储右括号和对应左括号的匹配关系，便于快速查找。
  2. 遍历字符串时，根据字符是左括号还是右括号，执行相应的逻辑。
  3. 栈用于跟踪未匹配的左括号，匹配成功时出栈，最终栈为空即为有效。

时间复杂度和空间复杂度

  • 时间复杂度：

    O(n)

    • 遍历字符串一次，每个字符入栈或出栈操作为 O(1)O(1)。

  • 空间复杂度：

    $O(n)$

    • 最坏情况下，栈需要存储字符串中所有的左括号。

此代码能够高效解决问题，并满足题目要求。

155. 最小栈

问题描述

设计一个支持 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.

提示：

  • $-2^{31} <= val <= 2^{31} - 1$
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 $3 * 10^4$ 次

题解

这个问题要求我们设计一个支持 push、pop、top 操作，并且能够在常数时间内返回最小元素的栈。为了高效地获取栈中的最小元素，我们需要在常数时间内访问最小值。

解题思路

我们可以通过 辅助栈 来实现这一功能：

  1. 栈 stack 存储所有的元素。
  2. 辅助栈 minStack 存储每个状态下的最小值。每次 push 操作时，minStack 会存储当前最小值。
    • 如果当前元素小于或等于 minStack 栈顶的元素，就将当前元素压入 minStack。
    • 否则，将 minStack 的栈顶元素再次压入 minStack，保持 minStack 栈顶始终为当前栈的最小值。
  3. 当调用 getMin 时，只需要返回 minStack 栈顶的元素即可。

代码实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <stack>
#include <iostream>
#include <vector>

class MinStack {
private:
    std::stack<int> stack;     // 主栈，用来存储数据
    std::stack<int> minStack;  // 辅助栈，用来存储当前栈中的最小元素

public:
    // 初始化栈
    MinStack() {}

    // 将元素压入栈中
    void push(int val) {
        stack.push(val);
        // 如果 minStack 为空，或者当前元素小于等于 minStack 栈顶，则也将其压入 minStack
        if (minStack.empty() || val <= minStack.top()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.top());
        }
    }

    // 删除栈顶元素
    void pop() {
        stack.pop();
        minStack.pop();
    }

    // 获取栈顶元素
    int top() {
        return stack.top();
    }

    // 获取当前栈中的最小元素
    int getMin() {
        return minStack.top();
    }
};

int main() {
    MinStack minStack;
    
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    
    std::cout << "getMin: " << minStack.getMin() << std::endl; // 返回 -3
    minStack.pop();
    std::cout << "top: " << minStack.top() << std::endl;       // 返回 0
    std::cout << "getMin: " << minStack.getMin() << std::endl; // 返回 -2

    return 0;
}

代码解释

  1. push(int val):
    • 将元素 val 推入主栈 stack。
    • 如果 minStack 为空，或者 val 小于或等于 minStack 栈顶的元素，说明 val 是当前栈的最小元素之一，因此将 val 压入 minStack。
    • 否则，复制 minStack 的栈顶元素到 minStack，保持 minStack 的栈顶为当前栈的最小值。
  2. pop():
    • 删除栈顶元素时，同时也删除 minStack 的栈顶元素，保证 minStack 的栈顶始终为当前栈的最小值。
  3. top():
    • 返回主栈 stack 的栈顶元素。
  4. getMin():
    • 直接返回 minStack 的栈顶元素，它始终保存着当前栈中的最小值。

时间复杂度

  • push 操作：每次都需要对两个栈进行 push 操作，因此时间复杂度为 $O(1)$。
  • pop 操作：每次都需要对两个栈进行 pop 操作，因此时间复杂度为 $O(1)$。
  • top 操作：直接访问栈顶，时间复杂度为 $O(1)$。
  • getMin 操作：直接访问 minStack 的栈顶，时间复杂度为 $O(1)$。

空间复杂度

  • 空间复杂度：$O(n)$，其中 n 是栈中元素的个数。我们需要两个栈来存储数据，因此空间复杂度是 $O(n)$。

这个解法确保了每个操作都能在常数时间内完成，并且使用了辅助栈来高效地追踪最小值。

394. 字符串解码

问题描述

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

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

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

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

示例 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]

题解

解题思路

这个问题可以通过使用栈（stack）来解决，栈能很好地帮助我们处理嵌套的结构。我们遍历字符串的每个字符并根据字符的不同类型进行相应的操作：

  1. 数字（k）：表示重复的次数，我们需要解析这个数字并保存下来。
  2. ’[‘：表示开始一个新的子串，遇到这个字符时，我们将当前的重复次数（k）和当前的子串入栈，准备开始处理新的子串。
  3. ’]’：表示当前子串的结束，我们从栈中弹出重复次数和之前的子串，然后将解码后的子串重复对应次数后与之前的子串拼接。
  4. 字母：直接拼接到当前的子串中。

代码实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <iostream>
#include <stack>
#include <string>

std::string decodeString(std::string s) {
    std::stack<int> numStack;  // 存储重复次数
    std::stack<std::string> strStack;  // 存储之前的字符串
    std::string currentStr = "";  // 当前构建的字符串
    int currentNum = 0;  // 当前的重复次数

    for (char c : s) {
        if (isdigit(c)) {
            // 如果是数字，构造完整的重复次数
            currentNum = currentNum * 10 + (c - '0');
        } else if (c == '[') {
            // 遇到'['时，将当前的重复次数和构建的字符串入栈
            numStack.push(currentNum);
            strStack.push(currentStr);
            currentNum = 0;  // 重置重复次数
            currentStr = "";  // 重置当前字符串
        } else if (c == ']') {
            // 遇到']'时，解码完成一个部分
            std::string temp = currentStr;
            currentStr = strStack.top(); strStack.pop();
            int repeatTimes = numStack.top(); numStack.pop();
            
            // 将当前部分重复并拼接到之前的字符串
            for (int i = 0; i < repeatTimes; i++) {
                currentStr += temp;
            }
        } else {
            // 普通字符直接加入当前字符串
            currentStr += c;
        }
    }

    return currentStr;
}

int main() {
    std::string s1 = "3[a]2[bc]";
    std::string s2 = "3[a2[c]]";
    std::string s3 = "2[abc]3[cd]ef";
    std::string s4 = "abc3[cd]xyz";
    
    std::cout << decodeString(s1) << std::endl; // 输出 "aaabcbc"
    std::cout << decodeString(s2) << std::endl; // 输出 "accaccacc"
    std::cout << decodeString(s3) << std::endl; // 输出 "abcabccdcdcdef"
    std::cout << decodeString(s4) << std::endl; // 输出 "abccdcdcdxyz"

    return 0;
}

代码解释

  1. numStack：存储每个子串需要重复的次数（k）。
  2. strStack：存储之前的字符串部分。在处理完一个子串并且发现新的子串时，当前的字符串会被保存在栈中。
  3. currentStr：当前正在构建的字符串。
  4. currentNum：当前的重复次数。
主要步骤
  1. 遍历字符串：
    • 如果遇到数字，则通过不断拼接来构造数字（k）。
    • 如果遇到 '['，表示开始一个新的编码子串，将当前数字和当前字符串入栈，开始新的子串构建。
    • 如果遇到 ']'，表示当前子串结束，需要从栈中弹出上一个子串和重复次数，拼接当前构建的子串。
    • 如果是字母，直接将其添加到当前构建的字符串中。
  2. 返回解码后的字符串：遍历完成后，currentStr 就是解码后的完整字符串。

时间复杂度

  • 时间复杂度：$O(n)$，其中 n 是字符串的长度。每个字符被访问一次，栈操作也是常数时间，因此时间复杂度是线性的。

空间复杂度

  • 空间复杂度：$O(n)$，栈中最多存储 n 个元素（在最坏的情况下，所有字符都是数字或者 '['，需要存储完整的字符串和数字），因此空间复杂度为线性。

例子解析

  1. 示例 1： 输入："3[a]2[bc]"
    • 第一步：构造子串 "a"，重复 3 次得到 "aaa"。
    • 第二步：构造子串 "bc"，重复 2 次得到 "bcbc"。
    • 最终结果为 "aaabcbc"。
  2. 示例 2： 输入："3[a2[c]]"
    • 第一步：构造子串 "c"，重复 2 次得到 "cc"。
    • 第二步：构造子串 "a" + "cc"，重复 3 次得到 "accaccacc"。
  3. 示例 3： 输入："2[abc]3[cd]ef"
    • 第一步：构造子串 "abc"，重复 2 次得到 "abcabc"。
    • 第二步：构造子串 "cd"，重复 3 次得到 "cdcdcd"。
    • 最终结果为 "abcabccdcdcdef"。

739. 每日温度

问题描述

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

  • $1 <= temperatures.length <= 10^5$
  • 30 <= temperatures[i] <= 100

题解

解题思路

这道题可以通过 单调栈 高效解决。具体思路如下：

  1. 使用一个栈（std::stack）存储数组下标，栈中的下标对应的温度值是 严格递减的。
  2. 遍历温度数组：
    • 如果当前温度比栈顶下标对应的温度高：
      • 栈顶下标出栈，计算当前天数与栈顶下标的天数差，记录到结果数组。
    • 将当前下标压入栈。
  3. 遍历结束后，栈中剩下的下标表示这些天之后没有更高温度，对应的结果填为 0。

这种方法的核心在于：

  • 栈中保存未处理的天数（即尚未找到更高温度的天数）。
  • 每个元素最多进栈和出栈一次，因此时间复杂度是 $O(n)$。

代码实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <vector>
#include <stack>
#include <iostream>

std::vector<int> dailyTemperatures(const std::vector<int>& temperatures) {
    int n = temperatures.size();
    std::vector<int> answer(n, 0); // 初始化结果数组为 0
    std::stack<int> indexStack;   // 存储数组下标的栈

    for (int i = 0; i < n; ++i) {
        // 当前温度比栈顶下标对应的温度高
        while (!indexStack.empty() && temperatures[i] > temperatures[indexStack.top()]) {
            int prevIndex = indexStack.top();
            indexStack.pop();
            answer[prevIndex] = i - prevIndex; // 计算天数差
        }
        // 将当前下标压入栈
        indexStack.push(i);
    }

    return answer;
}

int main() {
    std::vector<int> temperatures1 = {73, 74, 75, 71, 69, 72, 76, 73};
    std::vector<int> temperatures2 = {30, 40, 50, 60};
    std::vector<int> temperatures3 = {30, 60, 90};

    std::vector<int> result1 = dailyTemperatures(temperatures1);
    std::vector<int> result2 = dailyTemperatures(temperatures2);
    std::vector<int> result3 = dailyTemperatures(temperatures3);

    // 输出结果
    for (int r : result1) std::cout << r << " ";
    std::cout << std::endl;

    for (int r : result2) std::cout << r << " ";
    std::cout << std::endl;

    for (int r : result3) std::cout << r << " ";
    std::cout << std::endl;

    return 0;
}

代码解释

  1. 初始化：
    • 创建结果数组 answer 并初始化为全零。
    • 使用栈 indexStack 存储尚未找到更高温度的下标。
  2. 遍历数组：
    • 如果当前温度 temperatures[i] 大于栈顶下标对应的温度 temperatures[indexStack.top()]：
      • 弹出栈顶下标，计算两者的下标差 i - prevIndex，存储到结果数组。
    • 当前下标 i 入栈。
  3. 结束条件：
    • 遍历结束后，栈中剩余的下标在结果数组中已初始化为 0。

时间复杂度和空间复杂度

  • 时间复杂度：

    $O(n)$

    • 每个元素最多进栈和出栈一次，总体复杂度为 $O(n)$。

  • 空间复杂度：

    $O(n)$

    • 栈最多存储所有的下标，因此需要额外 $O(n)$ 空间。

示例解析

示例 1

输入：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

  • 第一天到第二天升温，answer[0] = 1。
  • 第二天到第三天升温，answer[1] = 1。
  • 第三天到第七天升温，answer[2] = 4。
  • ……
  • 最终结果：[1, 1, 4, 2, 1, 1, 0, 0]
示例 2

输入：temperatures = [30, 40, 50, 60]

  • 每天都有升温，结果为 [1, 1, 1, 0]。
示例 3

输入：temperatures = [30, 60, 90]

  • 每天都有升温，结果为 [1, 1, 0]。

84. 柱状图中最大的矩形

问题描述

给定 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 <=10^5$
  • $0 <= heights[i] <= 10^4$

题解

解题思路

这道题的目标是求出柱状图中能够形成的最大矩形的面积。一个有效的方法是利用 单调栈，通过栈来高效地计算每个柱子作为矩形的最小柱子时，能形成的最大矩形。

主要思路

  1. 单调栈：
    • 我们用栈来保存柱子的下标，栈中始终保持着一个单调递增的顺序。栈顶元素是目前遍历到的柱子的最小柱子（即它会是矩形的高度）。
    • 每当遇到一个比栈顶柱子高度小的柱子时，就意味着该柱子的矩形可以在栈顶元素之前结束。此时，我们就需要计算一个矩形的面积，矩形的高度是栈顶柱子的高度，宽度是当前柱子与栈顶柱子的下一个柱子之间的距离。
  2. 如何计算矩形面积：
    • 当栈顶元素出栈时，它的高度是矩形的高度，宽度是当前下标与栈顶元素的前一个元素之间的距离。这个距离就是 i - stack.top() - 1，其中 stack.top() 是栈中下一个比栈顶柱子矮的柱子的下标。
  3. 两边的边界：
    • 栈中的柱子代表了它们能够扩展的宽度，若遇到比栈顶小的柱子，我们就弹出栈顶元素，计算它能形成的最大矩形面积。
  4. 哨兵元素：
    • 为了避免边界问题，我们在数组的两端添加高度为0的柱子，确保所有的柱子都能出栈处理。

代码实现

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
32
33
34
35
36

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

int largestRectangleArea(std::vector<int>& heights) {
    // 在柱状图数组两端添加一个高度为 0 的哨兵柱子，方便计算
    heights.insert(heights.begin(), 0);
    heights.push_back(0);

    std::stack<int> stack;  // 用来存储柱子下标的栈
    int maxArea = 0;        // 记录最大面积

    for (int i = 0; i < heights.size(); ++i) {
        // 当当前柱子的高度小于栈顶柱子的高度时，弹出栈顶元素
        while (!stack.empty() && heights[i] < heights[stack.top()]) {
            int h = heights[stack.top()];  // 栈顶柱子的高度
            stack.pop();  // 弹出栈顶
            int width = i - stack.top() - 1;  // 计算宽度
            maxArea = std::max(maxArea, h * width);  // 更新最大面积
        }
        stack.push(i);  // 当前柱子的下标入栈
    }

    return maxArea;
}

int main() {
    std::vector<int> heights1 = {2, 1, 5, 6, 2, 3};
    std::vector<int> heights2 = {2, 4};
    
    std::cout << "Example 1: " << largestRectangleArea(heights1) << std::endl; // 输出 10
    std::cout << "Example 2: " << largestRectangleArea(heights2) << std::endl; // 输出 4

    return 0;
}

代码解释

  1. 哨兵元素：
    • heights.insert(heights.begin(), 0); 和 heights.push_back(0); 为了简化边界条件的处理，我们在数组两端插入了高度为0的柱子，这样可以保证栈中的柱子最终都会出栈。
  2. 遍历柱子：
    • 使用一个 stack 来存储柱子的下标。每次遇到一个比栈顶柱子低的柱子时，弹出栈顶柱子并计算其能形成的矩形面积。
    • 矩形的高度是栈顶柱子的高度，宽度是当前柱子的下标与栈顶柱子的前一个柱子之间的距离，即 i - stack.top() - 1。
  3. 计算矩形面积：
    • 通过 std::max 来更新最大矩形面积。
  4. 最终结果：
    • 通过遍历柱子并计算每个柱子形成的矩形的最大面积，最终返回最大面积。

时间复杂度和空间复杂度

  • 时间复杂度：$O(n)$，每个柱子最多进栈和出栈一次。
  • 空间复杂度：$O(n)$，栈最多存储 $O(n)$ 个元素。

示例解析

示例 1

输入：heights = [2, 1, 5, 6, 2, 3]

  1. 初始化：heights = [0, 2, 1, 5, 6, 2, 3, 0]
  2. 遍历数组，当 heights[3] 处于栈顶时，弹出栈顶，计算矩形面积为 5 * 1 = 5。
  3. 当 heights[4] 处于栈顶时，弹出栈顶，计算矩形面积为 6 * 1 = 6。
  4. 最终得到最大面积为 10。

示例 2

输入：heights = [2, 4]

  1. 初始化：heights = [0, 2, 4, 0]
  2. 遍历数组，弹出栈顶，计算矩形面积为 4 * 1 = 4。
  3. 最终最大面积为 4。
leetcode, hot100
C++ leetcode 栈
本文由作者按照 CC BY 4.0 进行授权