以下情况下的数据结构如何？ （最大堆栈）

Question

请注意，内存不受限制。 我需要从1插入INT到1000

我可以做以下每个操作都必须在恒定顺序的时间：

1. 推（）：增加了顶部
2. 流行（）：删除栈顶元素
3. GetMax的（）：返回最大元素

请建议我适当的数据结构。

Answer 1

由于没有内存限制，我将使用2个矢量 - 一个用于堆栈上的实际数据，另一个用于跟踪每个堆栈状态下的最大值。
为了简单起见，我假设这个堆栈只包含+ ve int。
我知道这没有任何错误检查。但我只是在这里提供数据结构的想法，而不是完整的解决方案。

class StackWithMax 
{ 
public: 
    StackWithMax() : top(-1), currentMax(0) { } 
    void push(int x); 
    int pop(); 
    int getMax() { return m[top]; } 
private: 
    vector<int> v; // to store the actual elements 
    vector<int> m; // to store the max element at each state 
    int top; 
    int currentMax; 
}; 

void StackWithMax::push(int x) 
{ 
    v[++top] = x; 
    m[top] = max(x, currentMax); 
} 

int StackWithMax::pop() 
{ 
    int x = v[top--]; 
    currentMax = m[top]; 
    return x; 
} 

Answer 2

对计数器使用正常堆栈结构和附加阵列 int c[1..1000]和变量int maxVal=0。

在代码的堆栈操作之后添加操作：

On push(x) -> c[x]++ ; maxVal = max(x,maxVal) 
On pop():x -> c[x]-- ; if (c[x] == 0) { j=x; while(c[--j] == 0); maxVal = j; } 

MAXVAL应该始终最大值。或许我错了，这应该有分期计算复杂度O（1）。 我一直在分析算法已经很长时间了。