-1

スタック内の最大値を見つけるための次のコードがあります。それは機能していますが、getMax() 関数を呼び出した後、スタックを表示できないため、最大値を見つけるために別のアプローチを使用する必要があります。

int Sorter:: getMax(){
    c.push(a.top());
    a.pop();
    while(!a.empty()){
            if(a.top() > c.top()){
            c.pop();
                    c.push(a.top());
                    a.pop();
            }
            else
                    a.pop();
    }
    return c.top();
}
4

5 に答える 5

3

副変数に最大値を保持します。

int max = a.top();
while(!a.empty()){
  c.push(a.top());
  a.pop()
  if(c.top() > max){
    max = c.top(); // find the maximum among the values of a.
  }
}

// This loop can be replaced with a.swap(c). As jogojapan mentioned.
// It is to demonstrate the principal.
while(!c.empty())
{
  a.push(c.top());  // return the values back into a
  c.pop();
}

return max;
于 2013-01-01T14:10:17.390 に答える
3

スタックのO(1)最大値を見つける時間とメモリの方法は次のとおりです。

  1. スタック内の各要素について、この要素の下に最大値を格納しましょう。
  2. 要素をプッシュすると、格納された (最大) 値はmax(st.top().value, st.top().maxValue)
  3. 要素をポップするときは、何も変更する必要はありません。

O(1)そのため、時間とメモリの複雑さにおいて、スタック内のすべての要素の最大値を取得できます。

擬似コード:

class StackWithMax
{
struct node
{
    int value; // an actual value;
    int maxValue; // maximum of below elements
};

stack<node> st;

public:
void pop()
{
    st.pop();
}

void push(const int &val)
{
   node newNode;
   newNode.value = val;
   newNode.maxValue = (st.empty() == true ? -INFINITY : max(st.top().maxValue, st.top().value) );
   st.push(newNode);
}

int maxStackValue() const
{
    assert(st.empty() == false);
    return st.top().maxValue;
}

};
于 2013-01-01T14:07:10.650 に答える
0

私がすることは、スタック全体を調べて答えを保存してから、secodn スタックを使用してオリジナルを再構築することです。

int Sorter:: getMax(){
    if(a.empty)
    {
        //handle this however you see fit
    }

    int res = a.top;
    //search for the maximum
    while(!a.empty()){
        if(a.top() > res){
            res = a.top();
        }
        c.push(a.top());
        a.pop();
    }

    //restore the original stack
    while(!c.empty()){
        a.push(c.top());
        c.pop();
    }
    return res;
}

余談ですが、「a」と「c」は不適切な変数名です。私はそれらをあなたのコードと一致させました。おそらく、もっと説明的なものを使用する必要があります。

于 2013-01-01T14:11:43.343 に答える
0

既に動作するコードがあるので、分析する必要があるのは次のとおりです。

  1. 既存のソリューションの時間の複雑さと空間の複雑さはどれくらいですか?
  2. すでにご存知かもしれませんが、時間と空間の間にはトレードオフがあります。時間の複雑さを改善するために、より多くの空間を使用できますか?
于 2013-01-01T14:01:34.870 に答える