栈
在数据结构的学习中，我们已经掌握了数组和链表等线性结构，它们支持在任意位置进行插入和删除操作。现在，我们将探讨一种具有特定约束的线性数据结构——栈（Stack）。这种约束性并非缺陷，而是栈的核心特征，使其在特定场景下展现出卓越的性能和简洁性。
栈是一种遵循后进先出（Last-In, First-Out, LIFO）原则的抽象数据类型。在栈中，元素的插入和删除操作都只能在同一个端点进行，这个端点称为栈顶（Top）。与栈顶相对的另一端称为栈底（Bottom）。栈的这种特性可以形式化地定义为：对于任意元素序列，最后插入的元素将最先被移除。
从形式化角度来看，栈可以定义为一个有序对 (S, op)，其中 S 是元素的集合，op 是定义在 S 上的操作集合。栈的核心约束在于：所有修改操作（插入和删除）都必须在栈顶执行，这确保了元素访问顺序的严格性。这种设计使得栈在函数调用管理、表达式求值、回溯算法等场景中具有不可替代的作用。
栈的基本操作
栈作为抽象数据类型，定义了以下基本操作接口。每个操作都有明确的前置条件和后置条件，以及确定的时间复杂度。
- 推入（Push）：操作将一个元素添加到栈顶。该操作的前置条件是栈已初始化，后置条件是栈的大小增加1，新元素成为栈顶元素。推入操作的时间复杂度为 O(1)。
- 弹出（Pop）：操作移除并返回栈顶元素。该操作的前置条件是栈非空，后置条件是栈的大小减少1，原栈顶的下一个元素成为新的栈顶。如果对空栈执行弹出操作，将引发下溢（Underflow）异常。弹出操作的时间复杂度为 O(1)。
- 查看栈顶（Top 或 Peek）：操作返回栈顶元素的值，但不移除该元素。该操作的前置条件是栈非空，后置条件是栈的状态不变。查看操作的时间复杂度为 O(1)。
- 判空（isEmpty）：操作检查栈是否为空，返回布尔值。该操作的时间复杂度为 O(1)。
- 获取大小（Size）：操作返回栈中当前元素的数量。该操作的时间复杂度为 O(1)，具体实现取决于底层数据结构的选择。
下面的流程图展示了栈操作的基本执行序列，栈顶元素用 C 表示：
这些基本操作构成了栈的完整接口。虽然操作集合简单，但通过它们的组合可以解决许多复杂的计算问题。
栈实验室
栈的实现
栈作为抽象数据类型，可以通过多种底层数据结构实现。不同的实现方式在时间复杂度、空间复杂度、缓存性能等方面存在差异。下面我们探讨两种主要的实现方式。
基于动态数组的栈
使用动态数组（在C++中为 std::vector）实现栈是最常见且高效的方式。在这种实现中，我们将数组的末尾作为栈顶，利用数组的连续内存布局和高效的尾部操作。
- 内存布局特性：动态数组在内存中连续存储元素，这种布局具有优秀的空间局部性（Spatial Locality）。当CPU访问栈顶元素时，相邻元素很可能已经被加载到缓存中，从而显著提升访问速度。每个元素的内存地址可以通过基址加上索引偏移量直接计算得出，访问时间为 O(1)。
- 扩容机制与摊销分析：当数组容量不足时，
std::vector 会执行扩容操作。典型的扩容策略是分配原容量两倍的新空间，然后将所有元素复制到新空间。虽然单次扩容的时间复杂度为 O(n)，但通过摊销分析（Amortized Analysis）可以证明，n 次推入操作的总时间复杂度为 O(n)，因此单次推入操作的摊销时间复杂度为 O(1)。
- 时间复杂度分析：基于动态数组的栈实现中，所有基本操作的时间复杂度如下：推入操作在最坏情况下为 O(n)（需要扩容），摊销时间复杂度为 O(1)；弹出操作为 O(1)；查看栈顶为 O(1)；判空和获取大小均为 O(1)。
让我们来看一个具体的C++实现：
#include <vector>
#include <stdexcept>
template <typename T>
class VectorStack {
private:
// 使用 std::vector 作为底层容器
// vector 的末尾索引对应栈顶位置
// 这种设计充分利用了连续内存的缓存优势
std::vector<T> elements;
public:
// 推入操作：将元素添加到栈顶
// 时间复杂度：摊销 O(1)，最坏情况 O(n)（扩容时）
void push(const T& item) {
// vector::push_back 在末尾添加元素
// 利用连续内存布局，访问效率高
基于链表的栈
链表实现栈的方式是将链表的头部作为栈顶。每次推入操作在链表头部插入新节点，弹出操作删除头部节点。这种实现方式的所有操作都保证在严格的 O(1) 时间内完成，不存在性能波动。
- 内存分配特性：链表节点通过动态内存分配创建，每个节点在堆内存中独立存在。节点之间通过指针连接，内存布局是非连续的。每个节点除了存储数据外，还需要额外的指针空间（在64位系统上通常为8字节）。
- 内存开销分析：假设存储类型 T 的大小为 sizeof(T)，每个节点需要 sizeof(T) + sizeof(Node*) 的内存空间。对于小数据类型（如 int），指针开销可能占比较大比例。此外，动态分配可能导致内存碎片化，降低内存利用率。
- 缓存性能：由于节点在内存中非连续分布，访问模式缺乏空间局部性。当访问栈顶节点时，下一个节点很可能不在同一缓存行中，需要额外的内存访问。这种跳跃式访问模式对CPU缓存不友好，实际运行速度通常低于数组实现。
#include <stdexcept>
// 链表节点结构体
template <typename T>
struct Node {
T data; // 节点存储的数据
Node* next; // 指向下一个节点的指针
// 构造函数：初始化节点数据，next 指针设为 nullptr
Node(const T& data) : data(data), next(nullptr) {}
};
template <typename T>
实现方式对比与选择
两种实现方式在多个维度上存在显著差异，选择时需要根据具体应用场景进行权衡。
- 时间复杂度对比：基于动态数组的实现中，推入操作的摊销时间复杂度为 O(1)，但在扩容时会出现 O(n) 的峰值。基于链表的实现中，所有操作都严格保证 O(1) 时间复杂度，不存在性能波动。
- 空间复杂度分析：动态数组实现的空间复杂度为 O(n)，其中 n 为元素数量。由于扩容策略，实际分配的空间可能略大于 n，但空间利用率通常较高。链表实现的空间复杂度也为 O(n)，但每个节点需要额外的指针开销，且可能存在内存碎片，实际空间利用率较低。
- 缓存性能差异：动态数组的连续内存布局具有优秀的缓存局部性。当访问栈顶元素时，相邻元素很可能在同一缓存行中，减少了缓存未命中的概率。链表的非连续内存布局导致缓存性能较差，每次访问都可能触发缓存未命中，需要从主内存加载数据。
- 适用场景：对于大多数应用场景，基于动态数组的实现是首选。它在平均情况下具有更好的性能，且实现简单。C++ 标准库中的
std::stack 默认使用 std::deque 作为底层容器，这是一种结合了数组和链表优点的数据结构。只有在需要严格保证每次操作都是 O(1) 且对性能波动极其敏感的场景（如实时系统、嵌入式系统）中，才考虑使用链表实现。
- 标准库使用：在实际开发中，推荐直接使用 C++ 标准库提供的
std::stack，它已经过充分优化和测试。std::stack 是一个容器适配器，默认使用 std::deque 作为底层容器，也可以指定使用 std::vector 或 std::list。
#include <stack>
#include <vector>
// 使用默认底层容器（std::deque）
std::stack<int> defaultStack;
// 指定使用 std::vector 作为底层容器
std::stack<int, std::vector<int>> vectorStack;
// 基本操作示例
vectorStack.push(10);
vectorStack.push(20);
int topValue = vectorStack.top(); // 20
vectorStack.
栈的应用
栈的 LIFO 特性使其在计算机科学的多个领域具有重要应用。下面我们探讨几个典型的应用场景。
函数调用与调用栈
在程序执行过程中，函数调用和返回的管理依赖于调用栈（Call Stack） 机制。调用栈是栈数据结构在运行时系统中的应用，用于维护函数调用的执行上下文。
栈帧（Stack Frame） 是调用栈中的基本单元，也称为活动记录（Activation Record）。每个栈帧包含以下信息：局部变量、函数参数、返回地址、调用者的栈帧指针、以及可能的临时计算结果。当函数被调用时，系统为其创建一个新的栈帧并推入调用栈；当函数返回时，对应的栈帧被弹出，控制权返回到调用者。
调用序列示例：假设 main 函数调用 functionA，functionA 又调用 functionB。调用栈的状态变化如下：首先 main 的栈帧被推入；然后 functionA 的栈帧被推入，位于 main 之上；接着 functionB 的栈帧被推入，位于栈顶。当 functionB 执行完毕返回时，其栈帧被弹出，控制权回到 functionA；functionA 返回时，其栈帧被弹出，控制权回到 main。
栈溢出（Stack Overflow）：调用栈的大小是有限的，通常由操作系统或编译器设置。当递归深度过大或局部变量占用空间过多时，可能耗尽栈空间，导致栈溢出错误。这是无限递归或深度递归算法中常见的问题。
后缀表达式求值
后缀表达式（Postfix Notation），也称为逆波兰表示法（Reverse Polish Notation），是一种不需要括号的数学表达式表示方法。在后缀表达式中，运算符位于其操作数之后。例如，中缀表达式 (3 + 4) * 5 对应的后缀表达式为 3 4 + 5 *。
算法描述：后缀表达式求值算法使用栈作为辅助数据结构。算法从左到右扫描表达式，遇到操作数时将其推入栈，遇到运算符时从栈中弹出所需数量的操作数，执行运算后将结果推入栈。算法的时间复杂度为 O(n)，其中 n 为表达式长度，空间复杂度为 O(n)。
执行过程示例：对于后缀表达式 3 4 + 5 *，执行过程如下：扫描到 3，推入栈，栈状态为 [3]；扫描到 4，推入栈，栈状态为 [3, 4]；扫描到 +，弹出 4 和 3，计算 3 + 4 = 7，将 7 推入栈，栈状态为 [7]；扫描到 5，推入栈，栈状态为 [7, 5]；扫描到 *，弹出 5 和 7，计算 7 * 5 = 35，将 35 推入栈，栈状态为 [35]。表达式扫描完毕，栈顶元素 35 即为最终结果。
中缀转后缀算法：将中缀表达式转换为后缀表达式同样可以使用栈实现。算法维护一个运算符栈，根据运算符优先级和结合性规则处理运算符。该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。
括号匹配
括号匹配是栈的经典应用之一。给定一个包含多种括号（圆括号、方括号、花括号）的字符串，判断其中的括号是否匹配。算法使用栈存储未匹配的左括号，遇到右括号时检查栈顶是否是对应的左括号。算法的时间复杂度和空间复杂度均为 O(n)，其中 n 为字符串长度。
深度优先搜索
在图的遍历算法中，深度优先搜索（Depth-First Search, DFS） 可以使用栈来实现。算法从起始顶点开始，将未访问的相邻顶点推入栈，然后从栈中弹出顶点进行访问，重复此过程直到栈为空。使用栈实现的 DFS 与递归实现等价，但提供了更明确的控制流程。
复杂度分析总结
下表总结了基于不同底层数据结构的栈操作的时间复杂度：
空间复杂度方面，两种实现均为 O(n)，其中 n 为栈中元素数量。动态数组实现的空间利用率通常更高，而链表实现存在指针开销和内存碎片问题。
小练习
- 如果只使用一个普通栈，getMin()操作的时间复杂度是？
4. 栈操作序列追踪练习
给定一个初始状态为空的栈，执行以下操作序列：push(10), push(20), top(), push(30), pop(), pop(), push(40), isEmpty(), pop(), pop(), isEmpty(), pop()。
请完整追踪整个操作序列的执行过程，并回答：
- 每次调用
top() 操作时，返回的元素值是什么？
- 每次执行
pop() 操作后，栈的内部状态如何变化？
- 每次调用
isEmpty() 操作时，返回值是 true 还是 false？
- 最后一次
pop() 操作会产生什么结果？
#include <iostream>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;
// 辅助函数：打印栈的内容（从栈顶到栈底）
string stackToString(stack<int> s)
{
if (s.empty()) return "[]";
vector<int> vec;
while
5. 最小栈数据结构设计练习
设计并实现一个扩展的栈数据结构，在支持标准栈操作（push(x)、pop()、top()）的基础上，额外提供 getMin() 操作，该操作需要在 O(1) 时间复杂度内返回栈中的最小元素。
要求：所有操作（push、pop、top、getMin）的时间复杂度均为 O(1)。
#include <iostream>
#include <stack>
#include <stdexcept>
using namespace std;
class MinStack
{
private:
// 主栈：存储所有元素
stack<int> mainStack;
// 辅助栈：存储每个状态下的最小值
// 辅助栈的栈顶元素始终等于主栈当前状态下的最小值
stack<int> minStack;
public:
MinStack()
{
// 栈会自动初始化
}
// 入栈操作 - O(1)
void push
6. 每日温度问题练习
给定一个整数数组 temperatures，其中 temperatures[i] 表示第 i 天的温度值。对于数组中的每个元素，计算需要等待多少天才能遇到一个更高的温度值。如果之后没有更高的温度，则结果为 0。
要求：返回一个整数数组 result，其中 result[i] 表示第 i 天需要等待的天数。使用单调栈方法解决，时间复杂度为 O(n)。
#include <iostream>
#include <vector>
#include <stack>
#include <sstream>
using namespace std;
// 辅助函数：打印数组
string arrayToString(const vector<int>& arr)
{
if (arr.empty()) return "[]";
stringstream ss;
ss << "[";
for
elements.push_back(item);
}
// 弹出操作：移除并返回栈顶元素
// 时间复杂度：O(1)
void pop() {
// 前置条件检查：防止对空栈执行弹出操作
if (isEmpty()) {
throw std::out_of_range("栈下溢：无法从空栈中弹出元素");
}
// vector::pop_back 移除最后一个元素，时间复杂度为 O(1)
elements.pop_back();
}
// 查看栈顶元素：返回栈顶元素的引用，不修改栈状态
// 时间复杂度：O(1)
T& top() {
// 前置条件检查：确保栈非空
if (isEmpty()) {
throw std::out_of_range("无法访问空栈的栈顶元素");
}
// vector::back 返回最后一个元素的引用
// 由于是连续内存，直接通过索引访问，时间复杂度 O(1)
return elements.back();
}
// 常量版本的 top 操作，用于 const 对象
const T& top() const {
if (isEmpty()) {
throw std::out_of_range("无法访问空栈的栈顶元素");
}
return elements.back();
}
// 判空操作：检查栈是否为空
// 时间复杂度：O(1)
bool isEmpty() const {
return elements.empty();
}
// 获取栈的大小：返回当前元素数量
// 时间复杂度：O(1)
size_t size() const {
return elements.size();
}
};
class LinkedListStack {
private:
// 指向链表头部的指针，头部节点对应栈顶
Node<T>* head;
// 元素计数器，用于 O(1) 时间获取栈大小
size_t count;
public:
// 构造函数：初始化空栈
LinkedListStack() : head(nullptr), count(0) {}
// 析构函数：释放所有动态分配的内存
// 时间复杂度：O(n)，n 为栈中元素数量
~LinkedListStack() {
// 依次弹出所有元素，释放每个节点的内存
while (!isEmpty()) {
pop();
}
}
// 拷贝构造函数和赋值运算符应被实现以避免浅拷贝问题
// 这里省略以保持代码简洁
// 推入操作：在链表头部插入新节点
// 时间复杂度：O(1)
void push(const T& data) {
// 1. 在堆内存中分配新节点
Node<T>* newNode = new Node<T>(data);
// 2. 将新节点的 next 指针指向当前头部
newNode->next = head;
// 3. 更新头部指针，新节点成为栈顶
head = newNode;
// 4. 更新元素计数
count++;
}
// 弹出操作：删除链表头部节点
// 时间复杂度：O(1)
void pop() {
// 前置条件检查
if (isEmpty()) {
throw std::out_of_range("栈下溢：无法从空栈中弹出元素");
}
// 1. 保存当前头部指针，用于后续内存释放
Node<T>* temp = head;
// 2. 将头部指针移动到下一个节点
head = head->next;
// 3. 释放原头部节点的内存
delete temp;
// 4. 更新元素计数
count--;
}
// 查看栈顶元素
// 时间复杂度：O(1)
T& top() {
if (isEmpty()) {
throw std::out_of_range("无法访问空栈的栈顶元素");
}
// 返回头部节点存储的数据
return head->data;
}
const T& top() const {
if (isEmpty()) {
throw std::out_of_range("无法访问空栈的栈顶元素");
}
return head->data;
}
// 判空操作
// 时间复杂度：O(1)
bool isEmpty() const {
// 头部指针为 nullptr 表示链表为空
return head == nullptr;
}
// 获取栈的大小
// 时间复杂度：O(1)
size_t size() const {
return count;
}
};
pop
();
(
!
s.
empty
())
{
vec.push_back(s.top());
s.pop();
}
// 反转，因为栈是后进先出，打印时应该从栈顶到栈底
reverse(vec.begin(), vec.end());
stringstream ss;
ss << "[";
for (size_t i = 0; i < vec.size(); i++)
{
ss << vec[i];
if (i < vec.size() - 1) ss << ", ";
}
ss << "]";
return ss.str();
}
int main()
{
stack<int> stk;
cout << "操作序列追踪：" << endl;
cout << "初始状态: 空栈" << endl;
cout << endl;
// push(10)
stk.push(10);
cout << "push(10) 后: " << stackToString(stk) << endl;
// push(20)
stk.push(20);
cout << "push(20) 后: " << stackToString(stk) << endl;
// top()
cout << "top() 返回: " << stk.top() << endl;
// push(30)
stk.push(30);
cout << "push(30) 后: " << stackToString(stk) << endl;
// pop()
int popped1 = stk.top();
stk.pop();
cout << "pop() 返回: " << popped1 << ", 栈状态: " << stackToString(stk) << endl;
// pop()
int popped2 = stk.top();
stk.pop();
cout << "pop() 返回: " << popped2 << ", 栈状态: " << stackToString(stk) << endl;
// push(40)
stk.push(40);
cout << "push(40) 后: " << stackToString(stk) << endl;
// isEmpty()
cout << "isEmpty() 返回: " << (stk.empty() ? "true" : "false") << endl;
// pop()
int popped3 = stk.top();
stk.pop();
cout << "pop() 返回: " << popped3 << ", 栈状态: " << stackToString(stk) << endl;
// pop()
int popped4 = stk.top();
stk.pop();
cout << "pop() 返回: " << popped4 << ", 栈状态: " << stackToString(stk) << endl;
// isEmpty()
cout << "isEmpty() 返回: " << (stk.empty() ? "true" : "false") << endl;
// pop() - 最后一次，会抛出异常
if (stk.empty())
{
cout << "pop() 抛出异常: 栈为空" << endl;
}
else
{
int popped5 = stk.top();
stk.pop();
cout << "pop() 返回: " << popped5 << endl;
}
return 0;
}
操作序列追踪：
初始状态: 空栈
push(10) 后: [10]
push(20) 后: [20, 10]
top() 返回: 20
push(30) 后: [30, 20, 10]
pop() 返回: 30, 栈状态: [20, 10]
pop() 返回: 20, 栈状态: [10]
push(40) 后: [40, 10]
isEmpty() 返回: False
pop() 返回: 40, 栈状态: [10]
pop() 返回: 10, 栈状态: []
isEmpty() 返回: True
pop() 抛出异常: Stack empty.
- top() 操作：返回栈顶元素
20，不改变栈的状态
- pop() 操作：依次弹出
30, 20, 40, 10，每次弹出后栈的状态都会改变
- isEmpty() 操作：
- 第一次调用时栈中有元素，返回
False
- 第二次调用时栈为空，返回
True
- 最后一次 pop()：当栈为空时执行
pop() 会抛出 InvalidOperationException 异常
- 栈的 LIFO 特性：最后入栈的元素（
30）最先出栈，体现了后进先出的特性
(
int
x
)
{
// 将元素推入主栈
mainStack.push(x);
// 如果辅助栈为空，或新元素小于等于当前最小值，更新辅助栈
if (minStack.empty() || x <= minStack.top())
{
minStack.push(x);
}
}
// 出栈操作 - O(1)
void pop()
{
if (mainStack.empty())
{
throw runtime_error("栈为空，无法弹出元素");
}
// 如果主栈栈顶等于辅助栈栈顶（即当前最小值），同时弹出辅助栈
if (mainStack.top() == minStack.top())
{
minStack.pop();
}
// 弹出主栈栈顶
mainStack.pop();
}
// 获取栈顶元素 - O(1)
int top()
{
if (mainStack.empty())
{
throw runtime_error("栈为空，无法访问栈顶元素");
}
return mainStack.top();
}
// 获取最小值 - O(1)
int getMin()
{
if (minStack.empty())
{
throw runtime_error("栈为空，无法获取最小值");
}
// O(1) 时间返回最小值
return minStack.top();
}
};
int main()
{
MinStack minStack;
minStack.push(5);
cout << "push(5) 后，最小值: " << minStack.getMin() << endl; // 5
minStack.push(3);
cout << "push(3) 后，最小值: " << minStack.getMin() << endl; // 3
minStack.push(7);
cout << "push(7) 后，最小值: " << minStack.getMin() << endl; // 3
minStack.push(2);
cout << "push(2) 后，最小值: " << minStack.getMin() << endl; // 2
minStack.pop(); // 弹出 2
cout << "pop() 后，最小值: " << minStack.getMin() << endl; // 3
minStack.pop(); // 弹出 7
cout << "pop() 后，最小值: " << minStack.getMin() << endl; // 3
cout << "当前栈顶: " << minStack.top() << endl; // 3
return 0;
}
push(5) 后，最小值: 5
push(3) 后，最小值: 3
push(7) 后，最小值: 3
push(2) 后，最小值: 2
pop() 后，最小值: 3
pop() 后，最小值: 3
当前栈顶: 3
- 设计思路：使用辅助栈存储每个状态下的最小值
- Push 操作：
- 将元素推入主栈
- 如果辅助栈为空或新元素 ≤ 辅助栈栈顶，将新元素也推入辅助栈
- Pop 操作：
- 如果主栈栈顶等于辅助栈栈顶（即当前最小值），同时弹出辅助栈
- 弹出主栈栈顶
- GetMin 操作：直接返回辅助栈栈顶，时间复杂度 O(1)
- 时间复杂度：所有操作均为 O(1)
- 空间复杂度：O(n)，辅助栈在最坏情况下需要存储 n 个元素
(
size_t
i
=
0
; i
<
arr.
size
(); i
++
)
{
ss << arr[i];
if (i < arr.size() - 1) ss << ", ";
}
ss << "]";
return ss.str();
}
// 每日温度问题 - 使用单调栈
vector<int> dailyTemperatures(const vector<int>& temperatures)
{
int n = temperatures.size();
vector<int> result(n, 0);
stack<int> stk; // 存储索引，栈中索引对应的温度值单调递减
for (int i = 0; i < n; i++)
{
// 当栈非空且当前温度大于栈顶索引对应的温度时
while (!stk.empty() && temperatures[i] > temperatures[stk.top()])
{
int prevIndex = stk.top();
stk.pop();
// 计算等待天数
result[prevIndex] = i - prevIndex;
}
// 将当前索引推入栈
stk.push(i);
}
// 栈中剩余的索引对应的结果值保持为 0（表示之后没有更高的温度）
return result;
}
int main()
{
vector<int> temperatures = { 23, 24, 25, 21, 19, 22, 26, 23 };
vector<int> result = dailyTemperatures(temperatures);
cout << "温度数组:" << endl;
cout << arrayToString(temperatures) << endl;
cout << "\n等待天数:" << endl;
cout << arrayToString(result) << endl;
cout << "\n详细分析:" << endl;
for (size_t i = 0; i < temperatures.size(); i++)
{
if (result[i] > 0)
{
cout << "第 " << i << " 天温度 " << temperatures[i]
<< "°C，等待 " << result[i] << " 天后遇到更高温度 "
<< temperatures[i + result[i]] << "°C" << endl;
}
else
{
cout << "第 " << i << " 天温度 " << temperatures[i]
<< "°C，之后没有更高温度" << endl;
}
}
return 0;
}
温度数组:
[23, 24, 25, 21, 19, 22, 26, 23]
等待天数:
[1, 1, 4, 2, 1, 1, 0, 0]
详细分析:
第 0 天温度 23°C，等待 1 天后遇到更高温度 24°C
第 1 天温度 24°C，等待 1 天后遇到更高温度 25°C
第 2 天温度 25°C，等待 4 天后遇到更高温度 26°C
第 3 天温度 21°C，等待 2 天后遇到更高温度 22°C
第 4 天温度 19°C，等待 1 天后遇到更高温度 22°C
第 5 天温度 22°C，等待 1 天后遇到更高温度 26°C
第 6 天温度 26°C，之后没有更高温度
第 7 天温度 23°C，之后没有更高温度
- 单调栈方法：使用单调递减栈存储索引，栈中索引对应的温度值保持单调递减
- 算法步骤：
- 初始化结果数组，所有元素设为 0
- 从左到右遍历温度数组
- 当栈非空且当前温度大于栈顶索引对应的温度时：
- 弹出栈顶索引
j
- 计算
result[j] = i - j
- 将当前索引推入栈
- 时间复杂度：O(n)，每个索引最多被推入和弹出栈各一次
- 空间复杂度：O(n)，最坏情况下所有索引都在栈中
- 关键思想：单调栈保证了当我们处理索引
i 时，栈中存储的是所有尚未找到下一个更高温度的索引