(真的很忙,所以博客记录得非常粗糙,见谅)
文章链接:https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
239. 滑动窗口最大值:https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
347.前 K 个高频元素:https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
自己看到题目的第一想法:几乎不怎么会做,也不怎么会和queue联系起来
看完代码随想录之后的想法:
1. 滑动窗口最大值:整体思路是有一个单调队列,然后一个数一个数的加入queue里的同时,看这个数是否比前一个数大,如果更大的话就把前面的数从后pop out,前面的数被pop了没有任何损失因为更小的在前面的数不重要了反正我们永远也不会选中它。queue里存的是nums的index,在i作为index中,i为nums下标,是要在[i - k + 1, i] 中选到最大值,只需要保证两点:a. 队列头结点需要在[i - k + 1, i]范围内,不符合则要弹出,b. 既然是单调,就要保证每次放进去的数字要比末尾的都大,否则也弹出;接着add这个元素,然后因为单调,当i增长到符合第一个k范围的时候(i>=k-1),每滑动一步都将队列头节点放入结果就行了
2. 前 K 个高频元素:先创一个hashMap,里面key是nums里的每个number,然后value是每个number出现的次数(实现方法:for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) +1);
});然后创建一个maxHeap里面存的是hashMap里的key+value且按照value的顺序从大到小排序(maxHeap的实现方法:PriorityQueue maxHeap =new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);)
自己实现过程中遇到哪些困难:第一道题我思路就理解了一辈子,然后第二题呢个maxHeap的创建方法我又理解了一辈子
今日收获,记录一下自己的学习时长:对队列的应用有了更清晰的认知,学习时长10小时