C++에서 O(1) 시간과 O(1) 추가 공간에서 스택에서 최대값 찾기

스택에 최대 요소를 저장할 수 있는 스택을 만들고 싶다고 가정합니다. 그리고 우리는 O(1) 시간에 그것을 얻을 수 있습니다. 제약 조건은 O(1) 추가 공간을 사용해야 한다는 것입니다.

최대 값을 저장할 사용자 정의 스택을 하나 만들 수 있습니다. pop 또는 peek과 같은 작업이 수행되면 최대 값이 반환됩니다. peek 작업의 경우 스택 상단과 최대 요소의 최대값을 반환하고 팝 작업의 경우 상단 요소가 더 클 때 인쇄하고 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