公司官方网站一般什么公司做,WordPress添加元素,做配资网站多少钱,长春师范大学目录 239. 滑动窗口最大值题目描述做题思路参考代码 347. 前 K 个高频元素题目描述参考代码 239. 滑动窗口最大值
题目描述
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每… 目录 239. 滑动窗口最大值题目描述做题思路参考代码 347. 前 K 个高频元素题目描述参考代码 239. 滑动窗口最大值
题目描述
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1
输入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 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2
输入nums [1], k 1
输出[1]做题思路
本题可以创建单调队列队首始终是滑动窗口中最大的元素。在窗口移动时如果移出的元素是最大元素那么队首元素出列。如果移入的元素比队尾元素小则队尾元素出列直到比队尾元素大。这样就保证了队列的元素单调递减。
参考代码
class MyQueue {DequeInteger deque new LinkedList();//弹出元素时比较当前要弹出的数值是否等于队列出口的数值如果相等则弹出//同时判断队列当前是否为空void poll(int val) {if (!deque.isEmpty() val deque.peek()) {deque.poll();}}//添加元素时如果要添加的元素大于入口处的元素就将入口元素弹出//保证队列元素单调递减//比如此时队列元素3,12将要入队比1大所以1弹出此时队列3,2void add(int val) {while (!deque.isEmpty() val deque.getLast()) {deque.removeLast();}deque.add(val);}//队列队顶元素始终为最大值int peek() {return deque.peek();}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length 1) {return nums;}int len nums.length - k 1;//存放结果元素的数组int[] res new int[len];int num 0;//自定义队列MyQueue myQueue new MyQueue();//先将前k的元素放入队列for (int i 0; i k; i) {myQueue.add(nums[i]);}res[num] myQueue.peek();for (int i k; i nums.length; i) {//滑动窗口移除最前面的元素移除是判断该元素是否放入队列myQueue.poll(nums[i - k]);//滑动窗口加入最后面的元素myQueue.add(nums[i]);//记录对应的最大值res[num] myQueue.peek();}return res;}
}347. 前 K 个高频元素
题目描述
给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
参考代码
class Solution {public int[] topKFrequent(int[] nums, int k) {MapInteger,Integer map new HashMap();//key为数组元素值,val为对应出现次数for(int num:nums){map.put(num,map.getOrDefault(num,0)1);}//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)PriorityQueueint[] pq new PriorityQueue((pair1, pair2)-pair2[1]-pair1[1]);for(Map.EntryInteger,Integer entry:map.entrySet()){//大顶堆需要对所有元素进行排序pq.add(new int[]{entry.getKey(),entry.getValue()});}int[] ans new int[k];for(int i0;ik;i){//依次从队头弹出k个,就是出现频率前k高的元素ans[i] pq.poll()[0];}return ans;}
}
