【代码随想录 | day13】(JavaScript) 栈和队列系列：239.滑动窗口最大值、347.前K个高频元素-烟雨网

theme: cyanosis
highlight: atom-one-dark

开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第8天，点击查看活动详情

239.滑动窗口最大值
347.前K个高频元素

239.滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。（注意：1 <= k <= nums.length）

返回 滑动窗口中的最大值 。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]

我的解法（超时）

针对题目给的例子，可以得到期望的答案，但是提交代码就会超出时间限制。应该是时间复杂度太高了。

定义好队列后，先找出一个滑动窗口大小的数组，放进队列中。这里考虑用for循环了，稍后会总结一波数组拷贝的内容。
设置一个循环，不断执行以下步骤：取得窗口中的最大值，然后窗口向右移动一位。

 var maxSlidingWindow = function (nums, k) {
   let queue = [];
   let res = [];
 
   // 先选出第一个窗口
   for (let i = 0; i < k; i++) {
     queue.push(nums[i])
   }
   console.log(queue);
 
   for (let j = k; j < nums.length; j++) {
     res.push(Math.max(...queue));
     queue.shift();
     queue.push(nums[j]);
   }
   res.push(Math.max(...queue));
   return res
 };

看了官方的解释，

对于长度为 n 的数组 nums 而言，窗口的数量为 n−k+1，因此该算法的时间复杂度为 O((n−k+1)k)=O(nk)，会超出时间限制，因此我们需要进行一些优化。

卡神解法

本题算比较有难度的，需要自己去构造单调队列，建议先看视频来理解。视频中说。自己去编写一个队列，实现队列中的元素单调递增或者单调递减

我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

主要思想是队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

 var maxSlidingWindow = function (nums, k) {
     
     class MonoQueue {
         queue;
         constructor() {
             this.queue = [];
         }
         enqueue(value) {
             let back = this.queue[this.queue.length - 1];
             while (back !== undefined && back < value) {
                 this.queue.pop();
                 back = this.queue[this.queue.length - 1];
             }
             this.queue.push(value);
         }
         dequeue(value) {
             let front = this.front();
             if (front === value) {
                 this.queue.shift();
             }
         }
         front() {
             return this.queue[0];
         }
     }
     
     
     let helperQueue = new MonoQueue();
     let i = 0, j = 0;
     let resArr = [];
     while (j < k) {
         helperQueue.enqueue(nums[j++]);
     }
     resArr.push(helperQueue.front());
     while (j < nums.length) {
         helperQueue.enqueue(nums[j]);
         helperQueue.dequeue(nums[i]);
         resArr.push(helperQueue.front());
         i++, j++;
     }
     return resArr;
 };

拿例子 nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 来解释

首先执行 let helperQueue = new MonoQueue(); helperQueue 是 MonoQueue 构造出来的实例对象。接着执行 class 中的构造函数，知道了对象 helperQueue.queue 是数组。
while (j < k) { helperQueue.enqueue(nums[j++]); }
- 首先 j 为 0 ，在不断 while 的过程中，通过实例对象中的 enqueue 方法，在 num 中将滑动窗口区域的元素，进行一个处理，然后放到 helperQueue.queue 中。怎么处理的呢？
- 将当前取得的 nums 中的元素记为 value 。先判断队列中最后一个数（back） 是否存在，如果存在那么和当前的 value 比较值的大小。当 value 更大一点的时候，就删除最后一个数，然后back又变为新数组的最后一个数。之后就把数值更大一点的 value 压入数组中。
- 那么经过此次 while 过后
- 可见数组里面的数是单调递减的，前面第一个元素就是我们需要的窗口内的最大值。可以通过实例对象的内置方法front()返回第一个元素，同时也删除了第一个元素。
接下来的 while 就是不断滑动窗口，此时 i = 0, j = 2
- 那么目前右移，遇到的就是 -3 了，首先还是执行 enqueue() 来判断能否进入队列。同样的，-3 加到了数组的最后，[3, -1, -3] 没有破坏单调性。
- helperQueue.dequeue(nums[i]); 这个时候 i 开始发挥作用了，此时 nums[i] = 1 。进入到函数 dequeue 中，则value就是 1 。貌似针对本例子，第一次调用这个函数没什么太大的作用？ 但是再仔细想想，之前的步骤中处理完的窗口，数组已经是[3, -1]了，那就算经过上一步的 enqueue()过后，数组为[3, -1, -3] ，那就不需要处理滑动窗口左边的数了。这也就理解大佬文章中写的如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
由此可以看到，虽然题目说了滑动窗口的大小为 k ，但是这一题我们通过设置一个单调递减的双头队列，就能得到想要维护的动态窗口，窗口长度是小于等于 k 的。

347.前K个高频元素

题目链接：347. 前 K 个高频元素 – 力扣（LeetCode）

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]

我的解法

以下代码通过没有AC，那为啥贴在这里？当然是为了分析咯😜

先讲一下我的思路吧：

统计数组中的字符出现次数，并且转为对象map
定义一个 max ，用来统计出现次数中的最大值。遍历 map 中的 key ，得到其出现的次数，当次数大于 max 时，就更新 max 为当前 key 所对应的最大值。
由于要找出前 k 个，所以循环 k 次。每次找到的最大值压入结果 res 里面，完了后删除map中所找到的这个结果，这样下次遍历的时候不会重复找出这个最大值。

 // 统计数组中的字符出现次数，并且转为对象
 var strToObj = function(arr) {
   let obj = {};
   for(let i = 0; i < arr.length; i++) {
       let item = arr[i]; // chars是字符串的每一个字符
       if(obj[item]) {
           obj[item]++;
       } else {
           obj[item] = 1;
       }
   }
   return obj
 }
 
 var topKFrequent = function(nums, k) {
   let res = [];
   let map = strToObj(nums);
   while (k--) {
     let max = 0; // 每次都重新计数
     for (var key in map) {
       if (map[key] > max) {
         max = map[key];
         res.push(parseInt(key))
         map[key] = undefined;
         // console.log(map);
       }
     }
   }
   console.log(res);
   return res
 };
 // @lc code=end
 // let nums = [1, 1, 1, 2, 2, 3], k = 2;
 let nums = [4,1,-1,2,-1,2,3], k = 2;
 topKFrequent(nums, k)

对于第一个例子nums = [1, 1, 1, 2, 2, 3], k = 2;是可以得到理想结果的。但是对于nums = [4,1,-1,2,-1,2,3], k = 2; 期望得到的是[-1,2] ，实际得到的是[ 1, 2, 3, -1 ]。

思路想法我觉得是可行的，虽然代码有点多且杂。。。

问题出在了while循环语句里面，for...in... 结构里面的语句。拿出错的例子来说，第一个遍历到的是 key: 1, value:1 此时已经大于max了，所以就被压入res里面了。后续的话，虽然 while 循环进行了k次，但是每次里面的 for 循环就压入了好几个数。由此，最后的结果出现的有的多！

改进：改动while循环里面的结构，上面代码中的strToObj()就不在这里重复写了。这个版本的代码通过率为100%

 var topKFrequent = function(nums, k) {
   let res = []; // 存放结果
   // 统计数组中每个数字出现的次数
   let map = strToObj(nums); 
   let maxNum; // map中的键，也就是数字
   while (k--) {
     let max = 0; // 出现的最大次数
     for (var key in map) {
       if (map[key] > max) {
         max = map[key];
         maxNum = parseInt(key);
       }
     }
     res.push(maxNum)
     map[maxNum] = undefined
   }
   return res
 };

卡神解法

大顶堆和小顶堆，这种数据结构特别擅长在一个很大的数据集里面求前k个高频或者低频之类的结果。

大顶堆：每个结点的值都大于或等于其左右孩子结点的值。小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额外的内存。堆仅仅使用数组，且不使用指针

js 没有堆需要自己构造，具体解法可以看链接。

代码随想录 (programmercarl.com)

总结

有一个很好用的，统计数组（或者字符串）中元素（或字符）出现的次数，在这里封装成函数，方便下次复用。

 var strToObj = function(arr) {
   let obj = {};
   for(let i = 0; i < arr.length; i++) {
       let item = arr[i]; // chars是字符串的每一个字符
       if(obj[item]) {
           obj[item]++;
       } else {
           obj[item] = 1;
       }
   }
   return obj
 }