スタック内の最大値を見つける最適化

Question

私の問題は、要素を挿入し、最後に挿入された要素をポップし、指定されたものにmaxを出力することです。私は目的のために2つのスタックを使用しており、利用可能な多くの提案テクニックに基づいて最適化されています。しかし、クエリの数がq< = 100000、テストケースが< = 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<<"Empty\n"; 
      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 << "Empty\n"; 
    else 
     std::cout << stack.top().second << "\n"; 
    } 
} 

あなたは、このように私たちはペアを削除し、単一のスタックを使用して、それを解決することができ、何のために挿入されたアイテムの履歴を使用していないようにまたそれが見えます。

リリースモードビルドのパフォーマンス（タイミング）は、最適化をオンにして測定することを忘れないでください。 （デバッグビルドでの性能を測定しないでください）