时间戳

首页 > 解决方案 > 在 O(1) 时间内找到堆栈中的最小元素 C++

c++ - 在 O(1) 时间内找到堆栈中的最小元素 C++

问题描述

在这里，我使用mini()函数查找堆栈中的最小元素。在堆栈中推送和弹出时，我设置min1和min2逻辑。在哪些情况下我的代码会失败？我的代码有什么问题？

push 函数集min1和min2变量。min1对应于最小元素并min2对应于堆栈中的第二个最小元素。在弹出中，如果弹出的元素等于 mini，那么我min1在弹出之前更新到第二个最小值并继续。所以在任何时候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;
}

标签： c++algorithmstackc++14minimum

解决方案

如果您可以将其他元数据作为堆栈中数据的一部分，您可以将在该点之前遇到的最少数据存储在元数据中。无论您弹出多少元素，堆栈顶部的元数据都将具有最小值。

推荐阅读