algo-aha

可取最大值的栈

• https://leetcode.com/problems/max-stack/
• https://leetcode.com/problems/min-stack/

再用个maxs栈保存当前nums栈的最大值。

class MaxStack {
    stack<int> nums;
    stack<int> maxs;
public:
    /** initialize your data structure here. */
    MaxStack() {
    }

    void push(int x) {
        if (maxs.empty() || x >= maxs.top()) maxs.push(x);
        nums.push(x);
    }

    int pop() {
        if (nums.top() == maxs.top()) maxs.pop();
        int ans = top(); nums.pop();
        return ans;
    }

    int top() {
        return nums.top();
    }

    int peekMax() {
        return maxs.top();
    }

    int popMax() {
        int ans = peekMax();
        stack<int> buffer;
        while (top() != ans) {
            buffer.push(pop());
        }
        maxs.pop();
        nums.pop();
        while (!buffer.empty()) {
            push(buffer.top());
            buffer.pop();
        }
        return ans;
    }
};

扩展：可取最大值的队列

用到最大值放队头的"单调递减队列"，见单调队列

频率栈

• https://leetcode.com/problems/maximum-frequency-stack/

按频率分桶，类似O(1)时间修改问题，但频率增加时小频率项保留

class FreqStack {
    // 每个频率一个桶；"有多个最大频率时，后进先出"，所以该桶是栈，栈中存放该频率的数
    unordered_map<int, stack<int>> buckets; // freq=>stack
    unordered_map<int, int> freq; // num=>freq
    int maxfreq = 0;
public:
    FreqStack() {
    }

    void push(int x) {
        buckets[++freq[x]].push(x);
        if (freq[x] > maxfreq) maxfreq = freq[x];
    }

    int pop() {
        int x = buckets[maxfreq].top(); buckets[maxfreq].pop();
        freq[x]--;
        if (buckets[maxfreq].empty()) maxfreq--;
        return x;
    }
};

只用栈操作，把栈排序成栈顶最小的递减序列

void sort(stack<int> &A) {
    // 先把B排成递增序列 <=> 找下一个更小的数
    stack<int> B;
    while (!A.empty()) {
        int a = A.top(); A.pop();
        while (!B.empty() && a < B.top()) {
            A.push(B.top());
            B.pop();
        }
        B.push(a);
    }
    // 把B倒回A
    while (!B.empty()) {
        A.push(B.top());
        B.pop();
    }
}