代码随想录算法训练营（JAVA）| 第五章 栈与队列part03

本文主要是介绍代码随想录算法训练营（JAVA）| 第五章 栈与队列part03，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

      今日任务 

力扣 239. 滑动窗口最大值、   347. 前 K 个高频元素

题目 ：239. 滑动窗口最大值

思路

滑动窗口问题，需要维护窗口内的最大值就行。

存在问题： 

                1.如何维护最大值？   

                2.当滑动窗口在移动时如何判定何时移出窗口内的最大值？

---

使用了一个自定义的双端队列（Deque）来维护窗口内元素的顺序，使得队列的头部始终是当前窗口的最大值。这种数据结构允许你在两端插入或删除元素，非常适合这个问题。

解释关键部分：

1. 自定义队列 MyQueue: 这个自定义队列通过维护一个递减序列来快速获取当前窗口的最大值。

   • poll(int val): 当窗口向右移动时，如果移出的元素是当前最大值（即等于队列头部元素），则将其从队列中移除。

   • add(int val): 向队列中添加新元素时，如果新元素大于队尾元素，则将队尾元素移除，直到队列为空或新元素不再大于队尾元素，以保持队列的递减特性。

   • peek(): 返回队列头部元素，即当前窗口的最大值。

2. 滑动窗口的移动:

   • 首先将前 k 个元素放入队列。

   • 对于每次窗口移动，移除窗口最前面的元素（如果它在队列中）并将新的元素加入窗口（同时也可能加入队列）。

   • 窗口每移动一次，就通过 peek() 方法取得当前窗口的最大值并存入结果数组。

索引判断逻辑：

• 在滑动窗口中，我们需要判断一个元素是否应该从队列中移除。这通过比较当前移出窗口的元素 nums[i - k] 和队列头部元素实现。如果相等，说明头部元素即为移出元素，应从队列中移除，保持队列头部元素为窗口的最大值。

• 当添加新元素时，我们移除所有小于该新元素的队尾元素，保证队列头部元素是最大的，这样就可以确保队列头部始终是当前窗口的最大值。

通过这种方式，MyQueue 能够在每个窗口位置快速提供最大值，而不需要对窗口内的所有元素重新排序或搜索，从而大大提高了算法的效率。

---

也就是说在add的时候，如果后一个值大于当前值那么就poll替换掉，队列中的元素是一个递减序列， 而如何随着窗口移动删除元素就是判断当前窗口的最大值是否等于遍历的值。

但是这样如何避免重复值的影响呢？

还是因为add的时候已经对队列中的值进行了处理？

在 add 方法中确实是通过不断移除队尾比新元素小的元素来维持队列的递减序列，这样确保了队头元素始终是当前窗口内的最大值。

关于重复值的处理，这里有几个关键点需要理解：

1. 递减队列的维护：当新元素加入队列时，add 方法确保了所有比新元素小的元素都会被从队尾移除。这意味着，如果有重复的最大值，只有最后一个被加入的最大值会留在队列中。这样，即使前面有相同的最大值，它们也不会影响到队列的递减性质。

2. 窗口移动时元素的移除：当窗口向右移动时，需要从窗口中移除一个元素（即窗口最左边的元素）。这时，只有当这个被移除的元素正好是队列头部的元素（即当前窗口的最大值）时，才会从队列中移除它。这个机制确保了即使有重复的最大值，只有当最大值真正离开窗口时，它才会从队列中被移除。

3. 重复值的影响：由于队列中保持的是递减序列，所以即使有重复值，也不会影响到获取当前窗口的最大值。如果有重复的最大值，它们会按照顺序存储在队列中，直到它们被移出窗口。这保证了即使在有重复值的情况下，队列头部元素始终是正确的最大值。

题解

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 index = 0;MyQueue myQueue = new MyQueue();for (int i = 0; i < k; i++ ) {myQueue.add(nums[i]);}// 记录对应最大值res[index++] = myQueue.peek();for (int i = k; i < nums.length; i++ ) {// 维护滑动窗口，移除myQueue.poll(nums[i - k]);// 维护滑动窗口，添加myQueue.add(nums[i]);// 记录对应最大值res[index++] = myQueue.peek();}return res;}}class MyQueue {Deque<Integer> 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();}
}

题目 ：347. 前 K 个高频元素

思路

本题我最先考虑的是暴力做法：用哈希表处理后统计，但是好像超时了，然后我又思考大顶堆，但是如果有多余限制的数要填入就不好搞了，所以就用小顶堆，但是我不知道该如何实现。看题解 吧     ：(

---

大顶堆解法

1. 创建哈希表： 首先，遍历整个数组，并用一个哈希表来记录每个元素出现的次数。

2. 使用优先队列（大顶堆）： 创建一个优先队列（Java中的PriorityQueue），根据元素出现的次数从大到小排列。这里，队列中存储的是一个包含两个元素的数组，第一个元素是数值本身，第二个元素是该数值出现的次数。

3. 填充队列： 遍历哈希表，将所有元素（即数字和它们的出现次数）加入到优先队列中。由于是大顶堆，出现次数最多的元素将会被放在队列的前面。

4. 提取结果： 从优先队列中取出前k个元素，这些就是出现频率最高的k个元素。

小顶堆解法

1. 创建哈希表： 同上，用哈希表记录每个元素出现的次数。

2. 使用优先队列（小顶堆）： 这次创建一个小顶堆，元素出现的次数从小到大排列。

3. 维护堆的大小： 遍历哈希表，对于每个元素，如果堆的大小小于k，直接添加到堆中。如果堆的大小已经是k，则检查当前元素的出现次数是否大于堆顶元素的出现次数，如果大于，就将堆顶元素弹出，将当前元素加入堆中。这样做的目的是保持堆中始终是出现次数最多的k个元素。

4. 提取结果： 最后，从堆中取出所有元素，这些就是出现频率最高的k个元素。

简化版代码解析

简化版代码实际上是小顶堆解法的一个简洁版本。它的核心逻辑与小顶堆相同，只是在代码表达上更加简洁和直观。它直接操作键值对转换为数组，然后将其添加到小顶堆中，保持堆的大小为k，最后依次取出堆中元素。

在这两种方法中，小顶堆的方法更优，因为它在最坏情况下的时间复杂度较低。大顶堆需要对所有元素进行排序，而小顶堆只需要维护大小为k的堆，这在k远小于n时特别有效。

---

啥是优先队列？？？

PriorityQueue 可以对其中元素进行排序，可以放基本数据类型的包装类（如：Integer，Long等）或自定义的类对于基本数据类型的包装器类，在内部通过堆（默认是小顶堆）来实现，确保队列头部总是优先级最低（或最高，取决于比较器）的元素。当你定义比较器时，你实际上是在告诉 PriorityQueue 如何确定元素之间的优先级。

• 小顶堆（最小堆）： 如果比较器是这样定义的 return a[1] - b[1];，那么元素 a 和 b 的比较结果基于它们频次的差值。如果 a 的频次小于 b 的频次，a 排在前面，这样队列头部就是频次最小的元素。

• 大顶堆（最大堆）： 如果你想要一个大顶堆，比较器应该反过来，return b[1] - a[1];，这样频次较高的元素会被放在队列的前面。

使用小顶堆是为了当堆的大小超过 k 时，可以轻松弹出频次最低的元素（即堆顶元素），保证堆中保留的是频次最高的 k 个元素。这种方式比大顶堆更有效，因为你不需要存储所有元素，只需要维护一个大小为 k 的堆。这在处理大数据集时特别有用，因为它可以显著减少内存使用。

---

实现逻辑

在这个循环中，我们不是一次性将所有元素添加到优先队列（小顶堆）中，而是通过一个动态的过程来添加元素。每次循环迭代时，都会执行以下步骤：

1. 创建数组： 对于 map 中的每个键值对（即每个元素及其出现次数），我们创建一个包含两个元素的数组 tmp。这个数组的第一个元素是原始数组的值（键），第二个元素是这个值出现的次数（值）。

2. 添加到优先队列： 将这个数组添加到优先队列 pq 中。由于 pq 是一个小顶堆，它会根据数组的第二个元素（出现次数）自动调整内部结构，确保队列头部是出现次数最少的元素。

3. 维护队列大小： 如果在添加元素后队列的大小超过了 k，那么我们会移除队列头部的元素。这样做是为了保持队列中只有出现次数最多的 k 个元素。因为每当我们添加一个新元素时，如果它的出现次数足够高，它就会留在队列中，而出现次数最少的元素会被移除。

题解

1.大顶堆

class Solution {public int[] topKFrequent(int[] nums, int k) {// key为数组元素值, val为对应出现次数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()) { // 遍历map，将所有元素按出现次数加入优先队列pq.add(new int[]{entry.getKey(), entry.getValue()});}int[] ans = new int[k]; // 存储结果for(int i = 0; i < k; i++) { // 从优先队列中取出前k个元素ans[i] = pq.poll()[0]; // 队列中元素是数组，数组第一个元素是原始数据}return ans;}
}

2.小顶堆

class Solution {public int[] topKFrequent(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()) {int[] element = new int[]{entry.getKey(), entry.getValue()};if(pq.size() < k) { // 如果队列未满，直接添加pq.add(element);} else if(entry.getValue() > pq.peek()[1]) { // 如果当前元素的出现次数大于堆顶元素，则替换pq.poll();pq.add(element);}}int[] ans = new int[k]; // 存储结果for(int i = k - 1; i >= 0; i--) { // 从优先队列中取出元素，由于是小顶堆，需要逆序填入结果数组ans[i] = pq.poll()[0];}return ans;}
}

3.小顶堆优化

class Solution {public int[] topKFrequent(int[] nums, int k) {// 创建小顶堆PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]); // 结果数组int[] res = new int[k]; // 用于统计元素出现次数Map<Integer, Integer> map = new HashMap<>(); // 统计频率for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);for(var x : map.entrySet()) {int[] tmp = new int[2]; // 创建数组存储元素及其频率tmp[0] = x.getKey();tmp[1] = x.getValue();pq.offer(tmp); // 添加到优先队列if(pq.size() > k) pq.poll(); // 维持队列大小为k}// 提取结果for(int i = 0; i < k; i++) res[i] = pq.poll()[0]; return res;}
}

代码解释：
 

1. 遍历哈希表的条目： for (var x : map.entrySet()) 这一行遍历了 map 中的所有条目。每个条目 x 是一个 Map.Entry 对象，它代表键值对。在这里，键是数组元素，值是该元素出现的次数。

2. 处理每个键值对： 在循环内部，创建一个临时数组 tmp，其中 tmp[0] 存储元素值（键），tmp[1] 存储该元素出现的次数（值）。这个数组代表了优先队列中的一个元素。

3. 将数组添加到优先队列： 通过 pq.offer(tmp) 将数组添加到优先队列中。由于优先队列是按照数组第二个元素（即频次）的升序排列的，因此队列头部始终是出现次数最少的元素。

4. 维护优先队列的大小： 如果队列的大小超过了 k，那么通过 pq.poll() 移除队列头部的元素，即移除出现次数最少的元素。这确保了队列中始终保留着出现次数最多的 k 个元素。

5. 提取结果： 最后一个循环通过 pq.poll()[0] 从优先队列中依次取出元素，并将这些元素的值（即原数组中的数字）存储到结果数组 res 中。由于队列是最小堆，所以这里实际上是从出现次数最少的元素开始取的，但由于我们只维护了出现次数最多的 k 个元素，所以最终 res 中存储的就是出现频率最高的 k 个元素。

通过这种方式，代码高效地找出了数组中出现频率最高的 k 个元素，同时避免了对整个数组进行排序，从而提高了效率。

FQA：

1.小顶堆普通版和优化版的区别在哪

小顶堆的普通版和优化版之间的主要区别在于它们处理元素和维护堆大小的方式。我们可以通过比较你提供的两个方法来具体理解这些差异：

普通版

• 堆的维护： 在普通版中，堆的维护发生在遍历哈希表时。对于每个元素，如果堆的大小小于 k，元素直接被添加到堆中。如果堆的大小等于 k 并且当前元素的频率大于堆顶元素的频率，则将堆顶元素弹出，并将新元素加入堆中。
• 效率： 这种方法在每次迭代中都可能对堆进行调整（添加或移除元素），这意味着它可能在整个过程中多次调整堆的内部结构，尤其是当遍历到的元素的频率较高时。
• 目的： 通过这种方式，我们保证了堆中始终存储的是当前遍历到的元素中频率最高的 k 个元素。这种方法减少了堆中存储的元素数量，因此可以减少内存使用。

优化版（简化版代码）

• 堆的维护： 在优化版中，堆的维护同样发生在遍历哈希表时，但这里的处理更简洁。无论堆的大小如何，每个元素都会被添加到堆中。只有当堆的大小超过 k 时，才会弹出堆顶元素，这样做保证了堆中始终保留着频率最高的 k 个元素。
• 效率： 优化版减少了不必要的比较和堆调整。它只在必要时（即堆的大小超过 k）才弹出堆顶元素，这通常会导致更少的操作，特别是当遇到频率较低的元素时。
• 目的： 这种方法同样保证了堆中存储的是频率最高的 k 个元素，但它通过尽可能延迟调整堆的操作来优化性能。

总的来说，普通版更加注重实时维护队列的大小，确保队列中始终是当前已处理的元素中频率最高的 k 个。而优化版则是先将所有元素加入队列，然后再调整队列，移除不必要的元素，最终保留频率最高的 k 个元素。优化版在很多情况下能够减少优先队列的操作次数，从而提高效率。

2.为什么优化版使用var？

在优化版代码中使用 var 是 Java 10 引入的局部变量类型推断的一个例子。当使用 var 声明一个变量时，编译器会根据变量初始化的值推断出变量的类型。这样做的目的是减少冗余的代码并提高可读性，特别是在变量类型很明显或类型名称很长的情况下。

for (var x : map.entrySet()) {int[] tmp = new int[2];tmp[0] = x.getKey();tmp[1] = x.getValue();pq.offer(tmp);if (pq.size() > k) pq.poll();
}

var x 被用在增强型 for 循环中。由于 map.entrySet() 返回的是 Set<Map.Entry<Integer, Integer>> 类型，编译器可以自动推断出 x 的类型是 Map.Entry<Integer, Integer>。这样，你就不需要显式地声明 x 的类型，使得代码更简洁。

使用 var 的优点包括：

1. 减少重复： 减少了代码中类型声明的重复性，特别是在类型声明非常明显的情境下。

2. 提高可读性： 当变量的类型很长或复杂时，使用 var 可以使代码更容易阅读。

3. 保持代码整洁： 使代码看起来更整洁，特别是在涉及复杂类型推断的场景中。

需要注意的是，使用 var 时必须同时进行变量的声明和初始化，否则编译器无法推断变量的类型。此外，在某些情况下，过度使用 var 可能会降低代码的可读性，特别是当变量的类型对于理解代码逻辑很重要时。因此，是否使用 var 需要根据具体情况和个人偏好来决定。

这篇关于代码随想录算法训练营（JAVA）| 第五章 栈与队列part03的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---