目录
🚩有效的括号
🌼最小栈
AC 栈
AC 链表
🌼字符串解码
🐻每日温度
🍒柱状图中的最大矩形
解释
AC 单调栈
🚩有效的括号
20. 有效的括号 - 力扣（LeetCode）
1，数据结构--栈
2，题目 “左括号必须以正确顺序闭合” -- 即，按栈的顺序，每一个新出现的右括号，必须被栈中相邻的左括号抵消掉
3，注意最后的 非空 检测
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2)
return false; // 奇数不匹配
unordered_map<char, char> m{
{'}','{'}, {')','('}, {']','['}
}; // 哈希：初始化构造
stack<char> st;
for (auto c : s) {
// 匹配到右括号
if (m.count(c)) {
if (!st.empty() && st.top() == m[c])
st.pop(); // 左右抵消
else
return false;
}
else
st.push(c);
}
if (!st.empty())
return false;
return true;
}
};🌼最小栈
155. 最小栈 - 力扣（LeetCode）
AC 栈
二元组 pair，用 second 维护最小值（注意声明方式 stack< pair<int, int> >）
push 时，second 取 getMin() 和 val 的较小值
getMin() 取 INT_MAX 或 st.top().second（当前最小值）
class MinStack {
private:
stack< pair<int, int> > st;
public:
MinStack() {
}
void push(int val) {
st.push({val, min(val, getMin())});
}
void pop() {
st.pop();
}
int top() {
return st.top().first;
}
int getMin() {
return st.empty() ? INT_MAX : st.top().second;
}
};AC 链表
链表模拟栈
思路类似 栈--二元组，Node 类里维护 val, Min, *next 三个变量
Node 如果是 class，要加 public，要不就用 struct
class Node {
public:
int val;
int Min; // 当前链表最小值
Node* next;
Node(int x, int y) : val(x), Min(y), next(NULL) {}
Node(int x, int y, Node* now) : val(x), Min(y), next(now) {} // 初始化构造
};
class MinStack {
private:
Node* head; // 头指针
public:
MinStack() {
head = NULL; // 初始化为空
}
void push(int val) {
if (head == NULL)
head = new Node(val, val);
else // 更新链表头节点 && 头节点的最小值
head = new Node(val, min(val, head->Min), head);
}
void pop() {
head = head->next;
}
int top() {
return head->val;
}
int getMin() {
return head->Min;
}
};🌼字符串解码
394. 字符串解码 - 力扣（LeetCode）
1，关键：'[' 左边一定是数字
2，思路：比如 abc3[r]，那么 x = "abc"，num = 3，所以字符串 = x + num * 'r'
3，坑：代码第 16 行
else if (c >= '0' && c <= '9')
// 而不是 c >= '1'，会跳过 100 里面的 04，括号嵌套的处理（可以用 abc3[w3[e]2[q]] 模拟下 ）（边模拟，边敲代码）
遇到左括号--压栈；遇到右括号--出栈
时间 O(S) ：S 为解码后字符串长度
class Solution {
public:
string decodeString(string s) {
stack< pair<string,int> > st;
string x = ""; // 左括号前的字符串
int num = 0; // 左括号左边的数字
for (auto c : s) {
if (c == '[') { // 遇到左括号，将左括号前的字母和数字压 入栈
st.push({x, num});
x = "";
num = 0;
}
else if (c >= 'a' && c <= 'z')
x += c; // 字符串
else if (c >= '0' && c <= '9')
num = num * 10 + (c - '0'); // 数字
else if (c == ']') { // 右括号，将右括号前的字母和数字 出栈
string s1 = st.top().first;
int n1 = st.top().second;
st.pop();
while (n1--)
s1 += x; // 字符串 + 数字 * 括号内字符串
x = s1; // 赋值给当前字符串
num = 0;
}
}
return x;
}
};🐻每日温度
739. 每日温度 - 力扣（LeetCode）
本题思路：单调栈（栈中元素单调递减 或 递增，不符合时用 while {... pop} 掉）
单调栈 - OI Wiki (oi-wiki.org)
1，栈存的是下标
2，如果遇到当前温度 > 栈顶温度，下标差就是栈顶那一天的天数差 day
3，坑，第 8 行，要用 while，否则会出现栈底积压了大量下标，但是数组已经遍历完的情况
while (!st.empty() && temperatures[i] > temperatures[st.top()] ) {O(n)：每个元素入栈出栈 1 次
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
stack<int> st; // 下标
vector<int> ans(n, 0); // 初始化为 0
for (int i = 0; i < n; ++i) {
while (!st.empty() && temperatures[i] > temperatures[st.top()] ) {
int day = i - st.top(); // 当前下标 - 栈顶下标 = 天数差
ans[st.top()] = day;
st.pop();
}
st.push(i); // 下标入栈
}
return ans;
}
};🍒柱状图中的最大矩形
84. 柱状图中最大的矩形 - 力扣（LeetCode）
解释
用单调栈解决👇
单调栈 - OI Wiki (oi-wiki.org)
1，stack 存的是索引，但是比较的是高度（单调递增栈的递增，是针对高度而言）
对应高度可以根据索引得到
2，递增不用理会，直到遇到递减的
需要对宽度分类讨论，如果栈为空，说明前面没有更短的，清空完更长的模板就没了
👇结合图理解
可以锯掉当前突出这块，也就是 pop() 掉，因为后面用不上了，宽度可以通过 索引 i 和 st.top() 计算得出，高度即当前栈顶木板 heights[st.top()]
注意顺序：先取高度，接着 pop()，最后对宽度分类讨论，然后更新 ans
AC 单调栈
时间 O(n)：每个元素只会出栈 1 次，不会出现每个 for 都需要出栈 n 次的情况，for 和 while 独立
所以时间线性
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st; // stack 存的是索引, 高度可以根据索引得到
heights.push_back(0); // 最后加个高度 0, 避免最后一直递增
int n = heights.size();
int ans = 0; // 最大矩形面积
for (int i = 0; i < n; ++i) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int h = heights[st.top()];
st.pop();
int wid;
if (st.empty()) // 栈为空, 左边只有 > 当前高度的, 已全部清空
wid = i;
else
wid = i - st.top() - 1;
ans = max(ans, h * wid);
}
st.push(i); // 插入索引
}
return ans;
}
};![[初阶数据结构] 包装类 | 泛型](https://img-blog.csdnimg.cn/direct/da10bc3e4da344b484428131f4c9f3fc.png)
