LeetCode 热题100 之 栈
1.有效的括号
思路分析：我们可以使用栈（stack）来解决这个问题。栈是一种先进后出的数据结构，这与括号匹配的需求非常契合。
- unordered_map<char, char> bracket_map：这个哈希表用来存储右括号与左括号的对应关系。比如 ‘)’ 对应 ‘(’，‘}’ 对应 ‘{’，] 对应 [。
- stack stk：我们使用栈来暂存左括号。当遇到右括号时，我们弹出栈顶元素，检查是否与当前右括号匹配。
- 遍历字符串：对于每个字符
- 如果是右括号，检查栈顶是否为与之匹配的左括号，如果不匹配，则返回false；
- 如果是左括号，直接入栈
- 栈的最终状态：如果栈为空，则说明所有的括号都匹配上了；如果栈为空，说明匹配失败，返回false
具体实现代码（详解版）：
class Solution {
public:
bool isValid(string s) {
// 创建一个哈希表，用于存储每个右括号对应的左括号
unordered_map<char, char> bracket_map = {
{')', '('},
{'}', '{'},
{']', '['}
};
stack<char> stk; // 栈用于存储左括号
// 遍历字符串中的每个字符
for (char c : s) {
// 如果是右括号，检查栈顶是否匹配
if (bracket_map.find(c) != bracket_map.end()) {
// 如果栈为空，说明没有对应的左括号
if (stk.empty() || stk.top() != bracket_map[c]) {
return false;
}
stk.pop(); // 匹配成功，弹出栈顶元素
} else {
// 如果是左括号，压入栈
stk.push(c);
}
}
// 最终栈应为空，如果栈不为空，则说明有未匹配的左括号
return stk.empty();
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
2.最小栈
思路分析：要做出这道题目，首先要理解栈结构先进后出的性质。对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。
按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
- 当一个元素要入栈时，取当前辅助栈的栈顶存储的最小值，与当前元素比较得到最小值，将这个最小值插入辅助栈中；
- 当一个元素要出栈时，要把辅助栈的栈顶元素也一并弹出；
- 在任意一个时刻，栈内元素的最小值就是存储在辅助栈的栈顶元素中。
具体实现代码（详解版）：
class MinStack {
stack<int> x_stack; // 主栈，用于存储所有元素
stack<int> min_stack; // 辅助栈，用于存储每一步的最小值
public:
// 构造函数，初始化 min_stack，将一个很大的值 (INT_MAX) 推入 min_stack 中，作为初始最小值。
MinStack() {
min_stack.push(INT_MAX); // 初始化时，辅助栈的栈顶是最大整数，表示最初没有最小值
}
// 将一个值压入栈
void push(int val) {
x_stack.push(val); // 将值压入主栈
// 将当前值和辅助栈栈顶的最小值进行比较，选择较小的一个压入辅助栈
min_stack.push(min(min_stack.top(), val));
}
// 弹出栈顶元素
void pop() {
x_stack.pop(); // 弹出主栈的栈顶元素
min_stack.pop(); // 弹出辅助栈的栈顶元素，保持栈同步
}
// 获取栈顶元素
int top() {
return x_stack.top(); // 返回主栈的栈顶元素
}
// 获取当前栈中的最小值
int getMin() {
return min_stack.top(); // 返回辅助栈的栈顶元素，它存储当前栈中的最小值
}
};
/**
* 用法示例：
* MinStack* obj = new MinStack(); // 创建一个新的 MinStack 对象
* obj->push(val); // 向栈中推入一个元素
* obj->pop(); // 弹出栈顶元素
* int param_3 = obj->top(); // 获取栈顶元素
* int param_4 = obj->getMin(); // 获取栈中的最小值
*/
- 时间复杂度度：O(1)
- 空间复杂度：O(n)
3.字符串解码
思路分析：这个问题是一个典型的栈问题，我们需要用栈来解决这个问题。解题的关键是通过遍历字符串并利用栈来处理嵌套的编码结构
- 遍历字符串
- 数字处理：遇到数字时，可能表示一个重复次数，需要将它组成一个完整的数字；
- ’['处理：将当前重复次数和当前字符串分别入对应的栈；然后需要对变量进行重置；
- ']'处理：意味着当前的子字符串已经结束。弹出栈顶的重复次数，重复当前的字符串（栈顶），并与之前的（解码好的）字符串拼接起来。
- 最好返回拼接的字符串。
具体实现代码(详解版）：
class Solution {
public:
string decodeString(string s) {
stack<int> count_stack; // 用于存储重复的次数
stack<string> string_stack; // 用于存储部分解码后的字符串
string current_string = ""; // 当前构建的解码字符串
int current_num = 0; // 当前重复次数
for (char c : s) {
if (isdigit(c)) {
// 如果是数字，构建重复的次数
current_num = current_num * 10 + (c - '0');
} else if (c == '[') {
// 遇到 '['，保存当前重复次数和当前字符串
count_stack.push(current_num);
string_stack.push(current_string);
current_string = ""; // 重置当前字符串
current_num = 0; // 重置重复次数
} else if (c == ']') {
// 遇到 ']'，进行解码操作
string temp = current_string;
current_string = string_stack.top(); // 获取上一个字符串
string_stack.pop();
int repeat_times = count_stack.top(); // 获取重复次数
count_stack.pop();
// 重复当前字符串，并拼接到之前的字符串
for (int i = 0; i < repeat_times; i++) {
current_string += temp;
}
} else {
// 如果是字母，直接加入当前字符串
current_string += c;
}
}
return current_string;
}
};
4每日温度
思路分析：我们需要找出每一天之后温度更高的那一天的天数。我们可以使用一个单调递减栈来解决这个问题。
- 栈的维护：栈中存储的是温度的索引。栈中的元素按温度从大到小排列，即栈顶元素所对应的温度是当前元素中最小的。
- 遍历温度数组：对于当前天数的温度 temperatures[i]，我们不断与栈顶索引对应的温度比较，若当前温度大于栈顶温度对应的温度，则说明找到了栈顶温度的下一个更高温度，弹出栈顶元素并计算天数差。
- 更新栈：无论是否弹出栈顶元素，当前天数的索引都会被压入栈中。
具体实现代码（详解版）
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> answer(n, 0); // 初始化为 0，表示没有找到更高温度的天数
stack<int> stk; // 栈用于存储温度的索引,即第几天
for (int i = 0; i < n; ++i) {
// 比较当前温度与栈顶温度的大小
while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
int idx = stk.top(); // 弹出栈顶元素的索引
stk.pop();
answer[idx] = i - idx; // 计算天数差并更新 answer 数组
}
stk.push(i); // 将当前天数的索引压入栈中
}
return answer;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
5.柱状图中最大的矩形
思路分析：我们可以使用 单调栈（Monotonic Stack）的方法，利用栈来优化查找每个柱子能够构成的最大矩形面积。
- 维护一个单调递增的栈：栈中保存的是柱子的索引，并且栈中的柱子高度是单调递增的。这样可以确保在遍历柱子时，我们可以快速地找到当前柱子能够形成的矩形的宽度
- 遍历柱子高度：
- 对于没应该柱子，检查它和栈顶柱子相比是否能够构成更大的矩形；
- 如果当前柱子的高度大于栈顶柱子的高度，直接将当前柱子的索引压入栈中；
- 如果当前柱子的高度小于栈顶柱子的高度，说明栈顶柱子已经找到了它更构成的最大矩形，应该弹出栈并计算矩形的面积。面积的计算需要使用当前柱子的索引来确定宽度，具体的：
- 如果栈为空，说明当前栈顶柱子从第一个柱子开始，到当前柱子的宽度是 i；
- 否则，矩形的宽度是当前柱子索引 i 和栈顶元素索引之间的差值减去 1。
- 处理完所有柱子之后，栈中可能还剩下未处理的柱子，它们的右边界已经到达数组的末尾。需要依次弹出栈中的元素并计算面积；
- 面积计算：每次弹出栈顶元素时，计算该元素作为矩形的高，并且矩形的宽度由当前索引和栈顶元素之前的索引差值来确定。
具体实现代码（详解版）：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> stk; // 单调递增栈，用来存储柱子的索引
int max_area = 0; // 最大矩形面积
heights.push_back(0); // 在末尾添加一个 0，确保栈能最终被清空
for (int i = 0; i < heights.size(); ++i) {
// 当前柱子的高度小于栈顶柱子的高度时，计算面积
while (!stk.empty() && heights[i] < heights[stk.top()]) {
int h = heights[stk.top()]; // 弹出栈顶元素，作为矩形的高
stk.pop();
int width = stk.empty() ? i : i - stk.top() - 1; // 宽度由当前索引和栈顶索引差值决定
max_area = max(max_area, h * width); // 更新最大面积
}
stk.push(i); // 将当前柱子的索引压入栈中
}
return max_area; // 返回最大矩形面积
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
单调栈是处理一类问题的强大工具，特别是与区间、顺序、范围、最大/最小值相关的题目。它的本质是维护栈中元素的顺序关系，使得栈中的元素满足某种单调性（单调递增或单调递减）。使用单调栈的主要目的是高效地查找满足条件的区间或值，从而减少了暴力解法中的时间复杂度。
单调栈常见步骤：
- 初始化栈：根据问题的需求，通常是存储元素的索引，有时也存储元素本身；
- 遍历数组：
- 对于每个元素，检查栈顶的元素是否满足特定的条件（例如，是否大于或小于当前元素）
- 如果满足条件，就弹出栈顶元素，并进行相关的计算（如更新最大面积或存储下一个更大面积的索引）
- 如果不满足条件或栈为空，将当前元素索引入栈
- 边界条件的处理：对于某些问题，最后可能栈中回残留一些未处理的元素，需要在遍历完成之和进行额外的计算（如计算剩余的矩形面积）
单调栈的核心思想是维护一个单调递增或单调递减的栈，通过栈的特点来高效处理一些需要查找、比较或计算区间最大值/最小值的问题。掌握如何使用单调栈来解决问题，可以帮助在算法中高效地处理一些常见的难题，并优化暴力解法的时间复杂度。