-1

我有以下代码用于查找堆栈中的最大值。它正在工作，但我应该使用另一种方法来查找最大值，因为在调用 getMax() 函数后，我无法显示堆栈 a。

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

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 回答
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 回答
0

由于您已经有了工作代码，因此您需要分析以下内容。

  1. 您现有解决方案的时间复杂度和空间复杂度是多少？
  2. 您可能已经知道，时间和空间之间存在权衡，您可以使用更多空间来实现更好的时间复杂度吗？
于 2013-01-01T14:01:34.870 回答
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

我认为如果允许临时变量，那么它变得非常容易。
算法：

将堆栈 A 的顶部元素放入临时变量 temp=StackA.top();
2. 从堆栈 A 中弹出一个元素并检查它是否大于临时变量的值。
2.1 如果是，则将值复制到 temp 并将其推送到堆栈 B。
2.2 否则只需将值推送到堆栈 B。
3. 重复步骤 2 直到堆栈 A 为空

我知道这看起来是一个明显的（而且没什么特别的）解决方案。但是它保留了堆栈的元素，当然如果您希望它们以相同的顺序排列，那么您可以再添加一个步骤来复制堆栈 B 中的所有弹出所有元素并将其推回堆栈 A。

于 2013-01-01T14:17:24.640 回答