思路
每一个新元素被 pop,他的出现次数,是他前一个出现相同元素的 次数 + 1
注意节约资源。代码
var FreqStack = function() { this.stack = []; this.disc = []; // 字典 帮助判断};/** * @param {number} x * @return {void} */FreqStack.prototype.push = function(x) { let count = 1; if(this.disc.indexOf(x) < 0) { // 不存在 this.disc.push(x); } else { // 之前确实有这个元素 从后向前找 let len = this.stack.length; for(let i = len -1; i >= 0; --i) { if(this.stack[i].value === x) { count += this.stack[i].count; break; } } } this.stack.push({ value: x, count });};/** * @return {number} */FreqStack.prototype.pop = function() { let list = []; let max = 0; let len = this.stack.length; let toRemoveIndex = -1; for(let i = len - 1; i >= 0; --i) { let obj = this.stack[i]; if(obj.count > max) { max = obj.count; list = [obj.value]; toRemoveIndex = i; } } this.stack.splice(toRemoveIndex, 1); return list[0];};/** * Your FreqStack object will be instantiated and called as such: * var obj = Object.create(FreqStack).createNew() * obj.push(x) * var param_2 = obj.pop() */复制代码