在C ++中以O(1)的时间查找堆栈中的最大值，并以O(1)的额外空间查找

假设我们要创建一个可以在堆栈中存储最大元素的堆栈。我们可以在O(1)时间内得到它。约束是，它应该使用O(1)额外的空间。

我们可以创建一个用户定义的堆栈，该堆栈将存储最大值，当执行一项操作（如pop或peek）时，将返回最大值。对于peek操作，返回top top的最大值和max元素；对于pop操作，当top元素较大时，返回它，然后打印并将max更新为2 * max – top_element。否则返回top_element。对于推送操作，将最大元素更新为x（要插入的数据），2 * x –最大。

示例

#include <iostream>
#include <stack>
using namespace std;
class CustomStack {
   stack<int> stk;
   int stack_max;
   public:
   void getMax() {
      if (stk.empty())
         cout << "Stack is empty"<<endl;
      else
         cout << "Maximum Element in the stack is: "<< stack_max <<endl;
   }
   void peek() {
      if (stk.empty()) {
         cout << "Stack is empty ";
         return;
      }
      int top = stk.top(); // Top element.
      cout << "Top Most Element is: "<<endl;
      (top > stack_max) ? cout << stack_max : cout << top;
   }
   void pop() {
      if (stk.empty()) {
         cout << "Stack is empty"<<endl;
         return;
      }
      cout << "Top Most Element Removed: ";
      int top = stk.top();
      stk.pop();
      if (top > stack_max) {
         cout << stack_max <<endl;
         stack_max = 2 * stack_max - top;
      } else
         cout << top <<endl;
      }
      void push(int element) {
         if (stk.empty()) {
         stack_max = element;
         stk.push(element);
         cout << "Element Inserted: " << element <<endl;
            return;
      }
      if (element > stack_max) {
         stk.push(2 * element - stack_max);
            stack_max = element;
      } else
         stk.push(element);
      cout << "Element Inserted: " << element <<endl;
   }
};
int main() {
   CustomStack stk;
   stk.push(4);
   stk.push(6);
   stk.getMax();
   stk.push(8);
   stk.push(20);
   stk.getMax();
   stk.pop();
   stk.getMax();
   stk.pop();
   stk.peek();
}

输出结果

Element Inserted: 4
Element Inserted: 6
Maximum Element in the stack is: 6
Element Inserted: 8
Element Inserted: 20
Maximum Element in the stack is: 20
Top Most Element Removed: 20
Maximum Element in the stack is: 8
Top Most Element Removed: 8
Top Most Element is:
6