第十一天——栈和队列（239. 滑动窗口最大值、347.前 K 个高频元素）

239. 滑动窗口最大值

学习链接

个人想法

1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作

2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

解题代码

这道题为什么不能直接存nums[i]:
原因在于如果直接存nums[i]，当当前滑动窗口的最大值 === 移出去的值，就会执行deque.shift()操作
扔掉当前最大值，导致问题，所以只存index，永远不会出现问题，因为index不会重复

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    let res = []
    let deque = []
    for(let i = 0;i < nums.length; i++){
        while(deque.length && deque[0] === i-k){ // 如果最大值是移走的数字就踢掉最大值
            deque.shift()
        }
        while(deque.length && nums[deque[deque.length - 1]] < nums[i]){ // 如果deque尾部小于当前值，全部pop
            deque.pop()
        }
        deque.push(i) // 填入nums[i]
        // 移动k个数才开始计算
        if(i >= k-1){
            res.push(nums[deque[0]])
        }
    }
    return res
};

347.前 K 个高频元素

学习链接

个人想法

解题代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const map = {}
    nums.forEach(item=>{
        if(map[item]){
            map[item]++
        } else{
            map[item] = 1
        }
    })
    const array = Object.entries(map) // [key,value]
    return array.sort((a,b)=> b[1] - a[1]).slice(0,k).map(i=>i[0])
};