（leetcode）LeetCode: 239. 滑动窗口最大值
1.思路一
滑动窗口最大值：两层for循环暴力遍历求解;（结果当然是超时…）
2.代码实现
1class Solution { 2 public int[] maxSlidingWindow(int[] nums, int k) { 3 4 int[] res = new int[nums.length]; 5 if (nums.length >= k) { 6 for (int i = 0; i < nums.length; i++) { 7 while (i + k <= nums.length) { 8 9 int temp = Integer.MIN_VALUE; 10 for (int j = i; j < i + k; j++) { 11 // 遍历出数组中的最大值？？？ 12 res[i] = Math.max(temp, nums[j]); 13 14 } 15 } 16 } 17 } 18 return res; 19 } 20}
3.复杂度分析
时间复杂度：两层for循环，O(n) * O(m),则时间复杂度简化为O(n²).
空间复杂度：创建数组res，则空间复杂度为O(n).
1.思路二
借用单调队列的弹出、加入等操作记录窗口内最大值，妙不可言~
2.代码实现
1class Solution { 2 public int[] maxSlidingWindow(int[] nums, int k) { 3 4 5 int len = nums.length - k + 1; // 预期结果数组长度 6 int[] res = new int[len]; // 创建结果数组 7 // 新数组索引为num 8 int num = 0; 9 // 前k个数组元素加入队列中 10 MyQueue myQueue = new MyQueue(); 11 for (int i = 0; i < k; i++) { 12 myQueue.add(nums[i]); 13 } 14 // 将最大值存储到数组中 15 res[num++] = myQueue.peek(); 16 // 窗口从k开始遍历 17 for (int i = k; i < nums.length; i++) { 18 19 // 出队列 20 myQueue.poll(nums[i - k]); 21 // 入队列 22 myQueue.add(nums[i]); // 入队的是当前元素！！！ 23 // 记录结果 24 res[num++] = myQueue.peek(); 25 } 26 return res; 27 28 } 29} 30 31class MyQueue { 32 Deque<Integer> deque = new LinkedList<>(); 33 34 public void poll(int val) { 35 if (!deque.isEmpty() && val == deque.peek()) { 36 deque.poll(); 37 } 38 } 39 40 public void add(int val) { 41 while (!deque.isEmpty() && val > deque.peek()) { 42 deque.removeLast(); 43 } 44 deque.add(val); 45 } 46 47 public int peek() { 48 return deque.peek(); 49 } 50}
3.复杂度分析
时间复杂度：一层for循环解决，则复杂度为O(n).
空间复杂度：创建了一个队列，则复杂度为O(n).
4.参考
LeetCode: 347.前 K 个高频元素
1.思路：
思路①：两层for循环，一层遍历记录，一层交换；
思路②：
2.代码实现
1// 未实现 2class Solution { 3 public int[] topKFrequent(int[] nums, int k) { 4 // 一层for循环将其出现的频率记录，需要定义一个数组记录,怎么记录？？map好像可以 5 int len = nums.length; 6 int[] res = new int[len]; 7 for (int i = 0; i < len; i++) { 8 9 } 10 // 一层for循环将前k个元素记录返回即可 11 Arrays.sort(res); 12 int[] nums1 = new nums1[k]; 13 for (int i = 0; i < res.length; i++) { 14 nums1[i] = res[i]; 15 } 16 return nums1; 17 } 18} 19 20// 正确使用map的姿势 21class Solution { 22 public int[] topKFrequent(int[] nums, int k) { 23 // 使用 HashMap 统计每个数字出现的次数 24 Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>(); 25 for (int num : nums) { 26 occurrences.put(num, occurrences.getOrDefault(num, 0) + 1); 27 } 28 29 // 使用优先队列（最小堆）来存储出现次数最大的 k 个数字 30 // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数 31 PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() { 32 public int compare(int[] m, int[] n) { 33 return m[1] - n[1]; // 按照出现次数升序排序 34 } 35 }); 36 37 // 遍历 HashMap 中的每个键值对 38 for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) { 39 int num = entry.getKey(); // 数字 40 int count = entry.getValue(); // 出现次数 41 42 // 如果优先队列已经有 k 个元素，则判断当前数字的出现次数是否大于队列中的最小值 43 // 如果是，则将队列中出现次数最小的元素出队，将当前数字入队 44 if (queue.size() == k) { 45 if (queue.peek()[1] < count) { 46 queue.poll(); 47 queue.offer(new int[]{num, count}); 48 } 49 } else { // 如果优先队列还没有 k 个元素，则直接将当前数字入队 50 queue.offer(new int[]{num, count}); 51 } 52 } 53 54 // 构造结果数组，将队列中的元素按照出现次数从大到小依次出队并放入结果数组中 55 int[] ret = new int[k]; 56 for (int i = 0; i < k; ++i) { 57 ret[i] = queue.poll()[0]; 58 } 59 60 return ret; 61 } 62}
3.复杂度分析
时间复杂度：一层map遍历，记作O(n),一层小顶堆遍历，记作O(logk),n个数组共记作O(nlogk).
空间复杂度：创建一个map，为O(n),创建一个队列，为O(k),创建一个数组，为O(k),故整体记作O(n).
4.参考
总结：
栈：先进后出（后进先出）递归的实现是栈：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中。
栈经典题目
括号匹配：是使用栈解决的经典问题。
字符串去重：可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。
逆波兰表达式问题：字符串去重逻辑一致。
三者处理逻辑相似，可以模板化。不同在于细节操作方式。
队列经典题目
队列：分为单边队列(Queue)和双边队列（Deque）,单边队列：先进先出。双端队列，前后两端均可进出。故可以当作栈使用。
滑动窗口最大值:队列采用弹出、加入操作实现对滑动窗口的移动和最值操作。加入和弹出操作细节有点绕。加入:需要循环判断入口值和当前值比较，如果当前值大于入口值，则弹出队列中所有小于当前值的值，直到入口值比当前值大.弹出:如果值等于入口值弹出，不等于则不操作，因为在加入的时候就对其进行比较操作了。
求前 K 个高频元素:思路很清晰，实现很陌生。需要使用map集合（记得前面刷题有遇到相似的情况）记录遍历之后的每个元素的频率。对其排序遍历返回即可
