使用双栈法可在常数时间内获取栈最大值：dataStack存储数据，maxStack同步记录每步最大值。入栈时，maxStack压入当前最大值；出栈时同步弹出。优化版仅当新值≥maxStack栈顶时才压入，减少空间占用，pop时若弹出值等于最大值则更新maxStack。
在C++中实现栈的最大值功能，核心目标是：在常数时间内获取当前栈中的最大元素，同时不影响栈的常规入栈（push）、出栈（pop）操作。通常做法是使用辅助栈来同步记录每个状态下的最大值。
基本思路：双栈法
使用两个栈：
- dataStack：存储实际数据。
- maxStack：存储对应 dataStack 每个状态下的最大值。
每当有新元素入栈时，maxStack 也压入当前的最大值（新值与原最大值的较大者）。这样 maxStack 的栈顶始终代表当前栈的最大值。
代码实现
#include#include
using namespace std;
class StackWithMax {
private:
stack
stack
public:
// 入栈
void push(int value) {
dataStack.push(value);
if (maxStack.empty() || value >= maxStack.top()) {
maxStack.push(value);
} else {
maxStack.push(maxStack.top());
}
}
// 出栈
void pop() {
if (dataStack.empty()) return;
dataStack.pop();
maxStack.pop();
}
// 获取栈顶元素
int top() {
if (dataStack.empty()) throw runtime_error("Stack is empty");
return dataStack.top();
}
// 获取最大值
int getMax() {
if (maxStack.empty()) throw runtime_error("Stack is empty");
return maxStack.top();
}
// 判断是否为空
bool empty() {
return dataStack.empty();
}
};
// 示例使用
int main() {
StackWithMax s;
s.push(3);
s.push(5);
cout s.push(2);
s.push(8);
cout s.pop();
cout // 实际上，按上面实现，maxStack 同步更新，pop后自动回到前一个最大值
return 0;
}
优化空间：节省内存的 maxStack
上面的方法简单直接，但 maxStack 和 dataStack 长度一致，占用较多空间。可以优化：maxStack 只在遇到更大或相等值时才压入。
立即学习“C++免费学习笔记（深入）”；
class StackWithMaxOptimized {private:
stack
stack
public:
void push(int value) {
dataStack.push(value);
if (maxStack.empty() || value >= maxStack.top()) {
maxStack.push(value);
}
}
void pop() {
if (dataStack.empty()) return;
int val = dataStack.top();
dataStack.pop();
if (val == maxStack.top()) {
maxStack.pop();
}
}
int getMax() {
if (maxStack.empty()) throw runtime_error("Stack is empty");
return maxStack.top();
}
// 其他方法类似... };
这种优化减少了 maxStack 的大小，只保存“关键”最大值节点。pop 时如果弹出的是当前最大值，才从 maxStack 中移除。
基本上就这些。两种方式都能实现 O(1) 时间获取最大值，第一种写法更直观，第二种更省空间。根据需求选择即可。
