Найти минимальный элемент в стеке за O (1) времени C ++

Question

Здесь я нахожу минимальный элемент в стеке, используя функцию mini(). Вставляя и вставляя в стек, я логически установил min1 и min2. В каких случаях мой код потерпит неудачу? Какие проблемы с моим кодом?

Функция push устанавливает переменные min1 и min2. min1 соответствует наименьшему элементу, а min2 соответствует 2-му наименьшему элементу в стеке. В элементе pop, если popped равен mini, я обновляю min1 до 2-го наименьшего значения перед pop и продолжаю. Таким образом, min1 всегда имеет наименьшее значение в стеке.

class stac
{
public:
void push(int item)
{
if(top>=STACK_SIZE-1)
{
    cout<<"Full"<<endl;
    return;
}
else
{
    if(item<min1)
    {
        min2 = min1;
        min1=item;
    }
    s[++top]=item;
    return;
}
}

void pop()
{
if(top==-1)
{
    cout<<"Empty"<<endl;
    return;
}
else
{
    if(s[top]==min1)
    {
        min1=min2;
    }
    top--;
    return;
}
}
void mini()
 {
   if(top==-1)
  {
      cout<<"no minimum"<<endl;
      return;
}
else
{
    cout<<min1<<endl;
}
}


private:
int min1 = INT_MAX;
int min2;
int s[STACK_SIZE];
int top = -1;
};
int main()
{

  stac s1;

  s1.push(5);
  s1.push(2);
  s1.push(9);
  s1.push(1);
  s1.push(24);
  s1.push(-1);
  s1.push(-87);
  s1.push(23);
  s1.mini();
  s1.display();

  return 0;
}

Answer 1

Вот ваш модифицированный код:

#include<iostream>
#include<string>

using namespace std;

#define STACK_SIZE 10000

class stac
{
public:

stac() : top(-1)
{

}

void push(int item)
{
if(top>=STACK_SIZE-1)
{
    cout<<"Full"<<endl;
    return;
}
else
{
    cout << "top is" << top << endl;
    int currentmin = min[top];
    top ++;
    if(top == 0 || item < currentmin )
    {
        min[top] = item; // New minimum
    }
    else
    {
       min[top] = currentmin; //keep current minimum
    }

    s[top]=item;

    return;
}
}

void pop()
{
if(top==-1)
{
    cout<<"Empty"<<endl;
    return;
}
else
{
    top--;
    return;
}
}
void mini()
 {
   if(top==-1)
  {
      cout<<"no minimum"<<endl;
      return;
}
else
{
    cout<<min[top]<<endl;
}
}

void display()
{
  int i = top;
  cout << "elememt stack:";

  while(i)
  {
     cout << s[i--] << " " ;

  }

  i = top;
  cout << "\nmin stack:";

  while(i)
  {
     cout << min[i--] << " " ;
  }
  cout << "\n";
}

private:

int s[STACK_SIZE];
int min[STACK_SIZE];
int top = -1;
};
int main()
{

  stac s1;

  s1.push(5);
  s1.push(2);
  s1.push(9);
  s1.push(1);
  s1.push(24);
  s1.push(-1);
  s1.push(-87);
  s1.push(23);
  s1.mini();
  s1.display();

  return 0;
}

Answer 2

Если бы вы могли иметь дополнительные метаданные как часть данных в стеке, вы могли бы хранить самые минимальные данные, встречающиеся до этой точки в метаданных. Независимо от того, сколько элементов вы вставляете, метаданные вершины стека будут иметь минимальное значение.

Answer 3

Проблема в том, что вы сохраняете только два последних минимума. После того, как вы получили два минимальных числа, вы не знаете, какое сейчас минимальное значение.

Держите два стека, один обычный, другой для поддержания текущего минимума. При нажатии всегда нажимайте текущий минимум на этом минимальном стеке. Таким образом, вы всегда будете иметь минимальное значение поверх текущего стека. Во время всплытия выскочите из обоих стеков.

Или в одном стеке вы всегда можете добавить два элемента, новый элемент вместе с новым минимумом. и во время всплывающего окна вытолкните два элемента, один текущий элемент, другой текущий минимум.