代码随想录训练营Day13|239.滑动窗口最大值，347.前K

239. 滑动窗口最大值

解题思路

• 构造单调递减序列 DecreQueue
• 滑动窗口移动时，队列既要pop弹出元素，也要push新的元素，但要保证单调递减
• pop：如果队列的尾部元素等于窗口移出的元素 value ，说明为此窗口的最大值，那么弹出该元素
• push: 如果队列的尾部元素小于窗口移进的元素，那么依次弹出小于 value 的元素，直到队列尾部的元素大于等于value时，push新的value值

var maxSlidingWindow = function(nums, k) {
    // 构造单调递减序列
    class DecreQueue {
        constructor() {
            this.queue = []
        }
        // 入队列
        enqueue(value) {
            let back = this.queue[this.queue.length - 1] // 队列尾部元素
            while (back !== undefined && back < value) {
                this.queue.pop() // 弹出队列里小于value的元素
                back = this.queue[this.queue.length - 1]
            }
            // 直到队列尾部的元素大于等于value时，push新的value值
            this.queue.push(value)
        }
        // 出队列
        dequeue(value) {
            // 队列头部元素等于value，弹出该值
            if (this.queue[0] === value) {
                this.queue.shift()
            }
        }
        front() {
            return this.queue[0]
        }
    }
    let myQueue = new DecreQueue();
    let i = 0;
    let j = 0;
    let resArr = [];
    while(i < k) {
        myQueue.enqueue(nums[i])
        i++
    }
    resArr.push(myQueue.front())
    while(i < nums.length) {
        myQueue.enqueue(nums[i])
        myQueue.dequeue(nums[j])
        resArr.push(myQueue.front())
        i++
        j++
    }
    return resArr
};

347. 前 K 个高频元素

解题思路

• 利用map统计每个元素出现次数
• 按次数降序排列，取前k个元素

var topKFrequent = function(nums, k) {
    let map = new Map()
    let res = []
    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], (map.get(nums[i]) || 0) + 1)
    }
    let sortArray = Array.from(map).sort((a, b) => b[1] - a[1])
    for (let i = 0; i < k; i++) {
        res.push(sortArray[i][0])
    }
    return res
};