备战蓝桥杯--栈

本文基于C++语言，在备战蓝桥杯算法竞赛过程中，通过对力扣Hot100栈相关题型的刷题和总结，归纳出栈的核心知识点、常用技巧和实战经验。后续也会持续更新具体题目解析，欢迎关注！

一、栈的基本概念与特性

1.1 什么是栈？

栈是一种后进先出（LIFO, Last In First Out） 的线性数据结构，只允许在栈顶进行插入和删除操作。想象一下生活中的叠盘子——你总是取最上面的盘子（最后放上去的），这就是栈的工作原理。

1.2 栈的ADT（抽象数据类型）

template <typename T>
class Stack {
public:
bool empty() const; // 判断栈是否为空
size_t size() const; // 返回栈中元素个数
T& top(); // 返回栈顶元素引用
const T& top() const; // 返回栈顶元素常量引用
void push(const T& val); // 入栈
void pop(); // 出栈
};

1.3 栈的实现方式对比

二、栈的核心应用场景

2.1 括号匹配 – 栈的经典应用

bool isValidParentheses(const string& s) {
stack<char> stk;
unordered_map<char, char> pairs = {
{')', '('}, {']', '['}, {'}', '{'}
};

for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
stk.push(c);
} else if (c == ')' || c == ']' || c == '}') {
// 栈为空或括号不匹配
if (stk.empty() || stk.top() != pairs[c]) {
return false;
}
stk.pop();
}
}
return stk.empty(); // 栈必须为空才算完全匹配
}

要点分析：

• 时间复杂度：O(n)，只需一次遍历

• 空间复杂度：O(n)，最坏情况下所有字符都入栈

• 关键点：遇到左括号入栈，遇到右括号检查栈顶是否匹配

2.2 表达式求值

int evaluateExpression(const string& expr) {
stack<int> nums; // 数字栈
stack<char> ops; // 运算符栈

auto calculate = [&]() {
if (nums.size() < 2 || ops.empty()) return;
int b = nums.top(); nums.pop();
int a = nums.top(); nums.pop();
char op = ops.top(); ops.pop();

switch(op) {
case '+': nums.push(a + b); break;
case '-': nums.push(a – b); break;
case '*': nums.push(a * b); break;
case '/': nums.push(a / b); break;
}
};

unordered_map<char, int> precedence = {
{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}
};

for (int i = 0; i < expr.length(); i++) {
if (expr[i] == ' ') continue;

if (isdigit(expr[i])) {
int num = 0;
while (i < expr.length() && isdigit(expr[i])) {
num = num * 10 + (expr[i] – '0');
i++;
}
i–; // 回退一步
nums.push(num);
} else if (expr[i] == '(') {
ops.push(expr[i]);
} else if (expr[i] == ')') {
while (!ops.empty() && ops.top() != '(') {
calculate();
}
if (!ops.empty()) ops.pop(); // 弹出'('
} else {
// 当前操作符优先级 <= 栈顶操作符优先级时，先计算
while (!ops.empty() && ops.top() != '(' &&
precedence[expr[i]] <= precedence[ops.top()]) {
calculate();
}
ops.push(expr[i]);
}
}

while (!ops.empty()) {
calculate();
}

return nums.top();
}

2.3 单调栈 – 解决"下一个更大元素"问题

vector<int> nextGreaterElements(const vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
stack<int> stk; // 存储索引

for (int i = 0; i < n * 2; i++) {
int idx = i % n;
while (!stk.empty() && nums[stk.top()] < nums[idx]) {
result[stk.top()] = nums[idx];
stk.pop();
}
// 只在实际的数组范围内入栈
if (i < n) {
stk.push(i);
}
}
return result;
}

单调栈要点：

• 保持栈内元素单调递减（或递增）

• 常用于：下一个更大/小元素、最大矩形面积、接雨水等问题

• 时间复杂度：O(n)，每个元素最多入栈出栈一次

三、C++ STL栈的使用详解

3.1 基本操作

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

void stackDemo() {
// 1. 创建栈
stack<int> s1; // 默认使用deque作为底层容器
stack<int, vector<int>> s2; // 使用vector作为底层容器

// 2. 入栈操作
s1.push(1);
s1.push(2);
s1.push(3);
s1.emplace(4); // 直接构造，C++11引入

// 3. 访问栈顶
cout << "栈顶元素: " << s1.top() << endl; // 输出4

// 4. 出栈
s1.pop(); // 移除4，不返回值

// 5. 容量查询
cout << "栈大小: " << s1.size() << endl;
cout << "是否为空: " << (s1.empty() ? "是" : "否") << endl;

// 6. 遍历栈（注意：栈没有迭代器，只能边pop边访问）
cout << "栈内容: ";
while (!s1.empty()) {
cout << s1.top() << " ";
s1.pop();
}
cout << endl;
}

3.2 实战技巧：栈的最小值问题

class MinStack {
private:
stack<int> dataStack; // 数据栈
stack<int> minStack; // 辅助栈，存储当前最小值

public:
MinStack() {}

void push(int val) {
dataStack.push(val);
// 如果minStack为空或新值<=当前最小值
if (minStack.empty() || val <= minStack.top()) {
minStack.push(val);
}
}

void pop() {
if (dataStack.empty()) return;

if (dataStack.top() == minStack.top()) {
minStack.pop();
}
dataStack.pop();
}

int top() {
return dataStack.top();
}

int getMin() {
return minStack.top();
}
};

设计要点：

• 使用两个栈分别存储数据和最小值

• 空间换时间，用O(n)额外空间实现O(1)的getMin操作

• 注意等于最小值的情况也要入辅助栈

四、综合实战案例

4.1 最大矩形面积（LeetCode 84）

int largestRectangleArea(vector<int>& heights) {
heights.push_back(0); // 添加哨兵，确保最后能清空栈
stack<int> stk;
int maxArea = 0;

for (int i = 0; i < heights.size(); i++) {
// 当前高度小于栈顶高度时，计算以栈顶为高的矩形面积
while (!stk.empty() && heights[stk.top()] > heights[i]) {
int height = heights[stk.top()];
stk.pop();

// 计算宽度
int left = stk.empty() ? -1 : stk.top();
int width = i – left – 1;

maxArea = max(maxArea, height * width);
}
stk.push(i);
}

heights.pop_back(); // 恢复原数组
return maxArea;
}

4.2 接雨水（LeetCode 42）（此题更深入的理解可看之前的博客）

int trap(vector<int>& height) {
stack<int> stk; // 存储索引
int water = 0;

for (int i = 0; i < height.size(); i++) {
while (!stk.empty() && height[i] > height[stk.top()]) {
int bottom = height[stk.top()];
stk.pop();

if (stk.empty()) break;

// 计算当前水槽的宽度和高度
int left = stk.top();
int width = i – left – 1;
int h = min(height[i], height[left]) – bottom;

water += width * h;
}
stk.push(i);
}

return water;
}

总结

栈作为基础数据结构，在算法竞赛和实际开发中都有着广泛的应用。掌握栈的关键在于：

栈的学习是一个循序渐进的过程，从基础操作到高级应用，再到复杂问题的解决，需要大量的练习和思考。建议从力扣的简单题开始，逐步挑战更复杂的问题，在实践中深化理解。

记住：栈不是万能的，但当发现问题的解决需要"最近相关性"时，栈很可能就是最佳选择！

祝大家在算法学习的道路上不断进步！有任何问题欢迎交流讨论。