网站建设书籍论文,河津北京网站建设,企业网站开发实训总结,提升学历方式239. 滑动窗口最大值 已解答 困难 相关标签 相关企业 提示 给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1#xff1… 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]提示 1 nums.length 105-104 nums[i] 1041 k nums.length class MyQueue {DequeInteger deque new LinkedList();void poll(int val) {if (!deque.isEmpty() val deque.peek()) {deque.poll();}}void 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();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 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums [1,1,1,2,2,3], k 2
输出: [1,2]示例 2: 输入: nums [1], k 1
输出: [1] 提示 1 nums.length 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的 进阶你所设计算法的时间复杂度 必须 优于 O(n log n) 其中 n 是数组大小。 class Solution {public int[] topKFrequent(int[] nums, int k) {MapInteger,Integer map new HashMap();for(int num:nums){map.put(num,map.getOrDefault(num,0)1);}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;}
}
主要是理解这个堆怎么用比较费劲
