数据结构设计：最大栈 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：数据结构设计：最大栈

评论礼仪 见这里，违者直接拉黑。

[fornobugworld]

感觉这个比LFU取巧了一点，push的时候保留之前的频率，然后pop的时候也是直接删除掉当前频率。 直观第一想法是push的时候还要修改之前频率，发现这样做pop时候做不到“取出最近添加的元素” 算是个小trick吧

[deepbreath373]

打卡

[zhangshuiyong]

关键是理解每个数出现的频率是连续的，例如5的频率，从1->2->3->4，有4频的5，必然有3频的5，maxFreq对应的不同数字的Stack为空可以，减少maxFreq--指向少一频的栈

[zhangshuiyong]

也可以设计一个数据结构，不需要maxFreq，VF表 + Stack<Stack>，由于频率连续，栈顶就是最大频率 = 外层Stack的长度，通过外层Stack索引下标=不同V的连续频率，可以像HaskMap那样离散地找到不同的频率对应的时序表

[jswxwxf]

js 版，直接通过关联数组，少维护一个 maxFreq

class FreqStack {
  constructor() {
    // 记录 FreqStack 中每个 val 对应的出现频率
    this._freqs = Object.create(null);
    // 记录频率 freq 对应的 val 列表
    this._freqVals = [];
  }

  push(val) {
    // val 对应的 freq 加一
    const freq = this._incr(this._freqs, val);
    // 在 freq 对应的列表加上 val
    this._push(this._freqVals, freq, val);
    // 更新 maxFreq
    this._maxFreq = Math.max(this._maxFreq, freq);
  }

  pop() {
    const vals = this._freqVals[this._freqVals.length - 1];
    const val = vals.pop();
    this._incr(this._freqs, val, -1);
    if (vals.length === 0) {
      this._freqVals.pop();
    }
    return val;
  }

  _incr(map, key, amount = 1) {
    let val = map[key];
    if (val === undefined) {
      val = 0;
    }
    const newVal = val + amount;
    if (newVal === 0) {
      delete map[key];
    } else {
      map[key] = newVal;
    }
    return newVal;
  }

  _push(map, key, val) {
    if (map[key] === undefined) {
      map[key] = [];
    }
    map[key].push(val);
  }
}

[awei-lwj]

CPP

// 这题和460. LFU 缓存 的设计思路差不多，只不过一个是栈一个是链表
// From Labulongdong的算法小抄
class FreqStack {
private:
    int maxFreq ;                            // 用来记录FreqStack中元素的最大频率
    unordered_map<int,int> valToFreq;        // val 对应的 frequency
    unordered_map<int,stack<int>> freqToVal; // freq对应的val

public:
    FreqStack() : maxFreq(0) {

    }
    
    void push(int val) 
    {
        int freq = valToFreq[val] + 1;
        valToFreq[val]++;               // val 对应的 frequency + 1

        // 修改 freq 对应的 val;
        freqToVal[freq].push(val);

        // 更新最大的maxFreq
        maxFreq = max(maxFreq,freq);
    }
    
    int pop() 
    {
        int val = freqToVal[maxFreq].top();
        freqToVal[maxFreq].pop();

        valToFreq[val]--;

        if( freqToVal[maxFreq].empty() )
        {
            maxFreq--;
        }     

        return val;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */

[zhongweiLeex]

关键是理解每个数出现的频率是连续的，例如5的频率，从1->2->3->4，有4频的5，必然有3频的5，maxFreq对应的不同数字的Stack为空可以，减少maxFreq--指向少一频的栈

确实 ，最主要的是需要理解 一个 freq 对应 一个 valuestack
不同的 freq 可能对应相同的 value