进一步优化堆栈中的最大值

Question

我的问题是插入一个元素，弹出最后一个插入的元素并在给定中打印最大。我正在为此目的使用2个堆栈，并根据大多数建议的技术进行优化。但是，我仍然需要对查询数量Q＆lt; = 100000和测试用例＆lt; = 100的情况进行进一步的优化。以下是我现在的代码：

int main() {
int t,q;
cin>>t;
char query;
int detail;
for(int test=0;test<t;test++)
{
    cout<<"Case "<<test+1<<":n";
    cin>>q;
    stack<int> s;
    stack<int> max;
    for(int i=0;i<q;i++)
    {
        cin>>query;
        if(query=='A')
        {
            cin>>detail;                    
            s.push(detail);
            if(max.empty())
                max.push(detail);
            else if(detail>=max.top())
                max.push(detail);
        }
        else if(query=='R')
        {
            if(!s.empty())
            {
                if(s.top()==max.top())
                    max.pop();
                s.pop();
            }
        }
        else
        {
            if(max.empty())
                cout<<"Emptyn";
            else
                cout<<max.top()<<"n";
        }
    }
}
return 0;
}

Answer 1

我不确定您的意思是'优化'是什么意思（在您的情况下最小化内存使用情况，改善执行时间或仅指算法效率）。以下来自 @alexeykuzmin0的评论，该代码看起来如下：

std::stack<std::pair<int, int>> stack;
for (int i = 0; i<q; i++)
{
  std::cin >> query;
  if (query == 'A')
  {
    std::cin >> detail;
    int max = stack.empty() ? detail : std::max(detail, stack.top().second);
    stack.push(std::make_pair(detail, max));
  }
  else if (query == 'R')
  {
    if (!stack.empty())
    {
       stack.pop();
    }
  }
  else
  {
    if (stack.empty())
      std::cout << "Emptyn";
    else
      std::cout << stack.top().second << "n";
  }
}

此外，看起来您没有为任何东西使用插入的项目的历史记录，因此我们可以将其删除并使用单个堆栈解决。

std::stack<int> stack;
for (int i = 0; i<q; i++)
{
  std::cin >> query;
  if (query == 'A')
  {
    std::cin >> detail;
    int max = stack.empty() ? detail : std::max(detail, stack.top());
    stack.push(max);
  }
  else if (query == 'R')
  {
    if (!stack.empty())
    {
      stack.pop();
    }
  }
  else
  {
    if (stack.empty())
      std::cout << "Emptyn";
    else
      std::cout << stack.top() << "n";
  }
}

还记得在发布模式构建中测量性能（时间），并进行优化。（不要衡量调试构建的性能）