代码随想录算法训练营第十三天|● 239. 滑动窗口最大值 ● 347.前 K 个高频元素 ● 总结

239. 滑动窗口的最大值

扣除主题链接(opens new window)

给定一个数组 nums，有一个大小为k的滑动窗口从数组的最左边移动到数组的最右边。您只能在滑动窗口中看到 k个数字。滑动窗口每次只向右移动一个。

返回滑动窗的最大值。

进阶：

你能在线性时间复杂性内解决这个问题吗？

提示：

• 1 <= nums.length <= 10^5
• -10^4<= nums[i]<= 10^4
• 1 <= k<= nums.length

思路：

难题，看完视频思路还是不懂，暂时放。

扣除主题链接(opens new window)

给定一个非空整数组，返回到频率之前 k 高的元素。

示例 1:

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

示例 2:

• 输入: nums = [1], k = 1
• 输出: [1]

提示：

• 你可以假设给定 k 总是合理的，而且 1 ≤ k ≤ 数组中不同元素的数量。
• 你的算法必须比时间更复杂 $O(n \log n)$ , n 是数组的大小。
• 题目数据保证答案是唯一的，换句话说，在数组中 k 高频元素的集合是唯一的。
• 您可以按任何顺序返回答案。

思路：

用map记录每个元素的出现频率，然后用优先级队列对出现频率进行排序。暂放。

需要掌握单调队列和优先队列，回头看看。