以下情況下的數據結構如何？ （最大堆棧）

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）。 我一直在分析算法已經很長時間了。