[LeetCode]Maximum Frequency Stack

这道题和LFU Cache很像，要稍微简单一点，我们不需要在Cache满的时候挑元素kick出去。这里我们思路也是类似的，对于每一个元素，我们需要统计其出现的次数，然后对于所有的出现次数，每一个出现次数会对应一个链表，存的是出现了所有这么多次的数字。我们再看题目要求的是，对于出现了同样次数的数字，我们也是按照入栈的顺序，所以我么可以把链表替换成stack，这样就成为次数和stack的一一map的关系。和LFU不同的是，我们插入或者删除，只对当前次数对应的stack进行操作，不会将其取出接着插入上一个或者下一个stack。换句话所，假设元素x出现了k次，那么从[1, k]对应的所有stack都会包含x，如果再插入，我们其k + 1对应的stack里接着插，pop的话我们就按照当前最大的frequency对应的stack pop即可。这样我们可以保证pop出当前元素x之后，其剩下的元素的k - 1个元素，其对应的每个次数，都仍然是按照原先的入栈顺序储存的。时间复杂度O(1)，空间复杂度O(n)，n为插入的次数，代码如下：