在之前刷力扣的过程中,我每刷道题都是先看题解然后再去边写边看,很多内容根本没消化,在进度上欺骗自己,感觉之前刷的都忘了,能力没有什么提升,现在还是一道都不会做。所以这次报了卡哥的算法训练营,希望能够按计划地有效刷题。本次刷题,我用的是 Java 语言解题,有余力的话也可能会加上 C++ 的题解。以下是算法训练营第十三天的刷题记录和思考笔记。
一、239 滑动窗口最大值 题目 给你一个整数数组 nums
,有一个大小为 k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k
个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。
1 2 3 4 5 6 7 8 9 10 11 输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
解题思路 这是使用单调队列的经典题目。此时我们需要一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。每次窗口移动的时候,调用 queue.pop()
(滑动窗口中移除元素的数值),queue.push()
(滑动窗口添加元素的数值),然后 queue.front()
就返回我们要的最大值。
遍历数组,保存当前窗口最大值的数组位置在双向队列中,保证队列中数组位置的数值按从大到小排序,并用 L
,R
来标记窗口的左边界和右边界。队列中保存的并不是真的数,而是该数值对应的数组下标位置,并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大,则需要弹出队尾值,直到队列重新满足从大到小的要求。刚开始遍历时,L
和 R
都为 0,有一个形成窗口的过程,此过程没有最大值,L
不动,R
向右移。当窗口大小形成时,L
和 R
一起向右移,每次移动时,判断队首的值的数组下标是否在 [L,R]
中,如果不在则需要弹出队首的值,当前窗口的最大值即为队首的数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int [] maxSlidingWindow(int [] nums, int k) { if (nums == null || nums.length < 2 ) return nums; LinkedList<Integer> queue = new LinkedList (); int [] result = new int [nums.length-k+1 ]; for (int i = 0 ;i < nums.length;i++){ while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){ queue.pollLast(); } queue.addLast(i); if (queue.peek() <= i-k){ queue.poll(); } if (i+1 >= k){ result[i+1 -k] = nums[queue.peek()]; } } return result; } }
二、347 前 K 个高频元素 题目 给你一个整数数组 nums
和一个整数 k
,请你返回其中出现频率前 k
高的元素。你可以按任意顺序返回答案。
1 2 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
解题思路 这道题目主要涉及到如下三块内容:要统计元素出现频率、对频率排序、找出前 K 个高频元素。
统计元素出现的频率,这一类的问题可以使用 map
来进行统计。然后是对频率进行排序,这里我们可以使用一种容器适配器就是堆,堆是一棵完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 class Solution { public int [] topKFrequent1(int [] nums, int k) { Map<Integer,Integer> map = new HashMap <>(); for (int num:nums){ map.put(num,map.getOrDefault(num,0 )+1 ); } PriorityQueue<int []> pq = new PriorityQueue <>((pair1, pair2)->pair2[1 ]-pair1[1 ]); for (Map.Entry<Integer,Integer> entry:map.entrySet()){ pq.add(new int []{entry.getKey(),entry.getValue()}); } int [] ans = new int [k]; for (int i=0 ;i<k;i++){ ans[i] = pq.poll()[0 ]; } return ans; } public int [] topKFrequent2(int [] nums, int k) { Map<Integer,Integer> map = new HashMap <>(); for (int num:nums){ map.put(num,map.getOrDefault(num,0 )+1 ); } PriorityQueue<int []> pq = new PriorityQueue <>((pair1,pair2)->pair1[1 ]-pair2[1 ]); for (Map.Entry<Integer,Integer> entry:map.entrySet()){ if (pq.size()<k){ pq.add(new int []{entry.getKey(),entry.getValue()}); }else { if (entry.getValue()>pq.peek()[1 ]){ pq.poll(); pq.add(new int []{entry.getKey(),entry.getValue()}); } } } int [] ans = new int [k]; for (int i=k-1 ;i>=0 ;i--){ ans[i] = pq.poll()[0 ]; } return ans; } }
三、栈与队列的总结 栈的应用在对称性问题上,如括号匹配问题、字符串去重问题、逆波兰表达式问题。
单调队列和优先级队列。