实现一个栈，使得出栈、入栈、获取最大值的时间复杂度为O(1)

本文主要是介绍实现一个栈，使得出栈、入栈、获取最大值的时间复杂度为O(1)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：用C++实现一个栈，使得出栈、入栈、获取最大值的时间复杂度为O(1)

思路：用2个栈，其中一个叫数据栈，用来做入栈、出栈操作，第二个叫最大值栈，用来返回最大值。
①在某个元素入栈的时候，先往数据栈里压入元素。同时判断本元素是否大于等于最大值栈的栈顶元素，如果大于等于，就把它压入最大值栈，否则丢弃
这里有个很巧妙的设计，当元素小于当前最大值时不把它压入最大值栈，而是直接丢掉，是没问题的。因为只要该元素还在数据栈里，前面出现的最大值也一定在数据栈里，所以最大值轮不到它。一旦最大值从数据栈里弹出了，该元素肯定也早就弹出了，更加轮不到它。所以它永远成为不了最大值。
②在出栈时，首先是数据栈先出栈，然后判断出栈元素是否为最大值，即最大值栈的栈顶元素，如果是，就在最大值栈里也把它出栈。如果不是，那最大值栈就不动。
③获取最大值，就返回最大值栈的栈顶元素即可。
时间复杂度都是O(1)。

#include <stack>
#include <iostream>class MaxStack {
public:void push(int value) {dataStack.push(value);if (maxStack.empty() || value >= maxStack.top()) {maxStack.push(value);}}void pop() {if (dataStack.top() == maxStack.top()) {maxStack.pop();}dataStack.pop();}int top() {return dataStack.top();}int getMax() {return maxStack.top();}private:std::stack<int> dataStack;std::stack<int> maxStack;
};int main() {MaxStack stack;stack.push(5);stack.push(8);stack.push(3);//3不用存入最大值栈，因为只要3在，8就在，3永远不可能是最大值std::cout << stack.getMax() << std::endl; // 8stack.pop();std::cout << stack.getMax() << std::endl; // 8stack.pop();std::cout << stack.getMax() << std::endl; // 5return 0;
}