算法训练营Day12
#Java #Review
Feeling and experiences：
滑动窗口最大值:力扣题目链接
给定一个数组 nums，有一个大小为?k?的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k?个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
目前为止出现的第一道Hard。
最开始想到的就是暴力解法，而且很容易能写出来
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
result[i] = max;
}
return result;
}
}但是这样提交就超时了
作为Hard题，肯定不会这么容易就能通过。
但是在这之后，我没有想到更好的办法了，直接看了代码随想录的视频题解：单调队列！
视频中的思路使用的单调栈。
单调栈的特点是栈内的元素保持调性，可以是单调递增或者单调递减。
严格来说的话应该用的是单调双端队列（思路是一样的）， 思路归纳：
1. 维护递减栈：
???-?对于单调递减栈，栈内的元素是递减的。这意味着栈底元素是整个栈中的最大值，而栈顶元素是最小的。这是因为当遇到一个新元素时，我们需要将栈中比它小的元素弹出，以便新元素成为当前窗口的最大值。
2. 栈中存储元素的特殊含义：
???-?在滑动窗口问题中，我们并不直接在栈中存储元素的值，而是存储元素的索引。这是为了在维护递减栈的过程中，能够方便地判断元素是否在当前窗口范围内，以及计算窗口的大小。
3. 遍历数组并维护栈：
???-?从左到右遍历数组，对于每个元素：
??????-?移除过期的元素：检查栈顶元素是否超出当前窗口的范围，如果是则弹出。
??????-?保持递减性：将栈中比当前元素小的元素弹出，以保持递减栈的性质。
??????-?将当前元素的索引入栈。
4. 记录结果：
???-?当遍历到形成一个完整窗口的位置时，即窗口大小达到设定值时，可以从栈底获取当前窗口的最大值。这是因为栈底元素对应的索引是最早进入窗口的元素，同时它是窗口中的最大值。
创建一个Deque（双端队列），来表示一个动态且元素严格单调的滑动窗口。
创建一个result数组来存放结果。
注意：双端队列中存放的下标，而不是原数组中的数。
模拟如下：
假如题目原数组：【2，5，3，4，1】，k = 3（滑动窗口的容量）
下标分别为0，1，2，3，4
在双端队列中进行入队出队操作（单调递减）：
注意：操作的是下标值！
队列最左边的数就是当前窗口下的最大值！
代码解释如下：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//创建一个双端队列，进行入队出队操作（注意：操作的是下标）
Deque<Integer> deque = new LinkedList<>();
int index =0;
//创建一个数组来记录结果，容量为num.length-k+1; 因为手动模拟发现，到length-k个数时就有length-k个最大值，最后k个数里面再出1个，这样就会有length-k+1个最大值
int []res = new int[nums.length-k+1];
for(int i =0;i<nums.length;i++){
//对过期的元素进行删除
if(!deque.isEmpty() && deque.peek() == i-k){
//队列中队头的数超过生命周期
deque.remove();
}
while(!deque.isEmpty() && nums[i] > nums[deque.peekLast()]){
deque.removeLast();//严格递减
}
deque.add(i);
//记录结果
if(i >=k-1)
res[index++] = nums[deque.peek()];
}
return res;
}
}其实思路很简单，只要能手动模拟出来，代码是很简单的。
第一要注意到双端队列存的是下标！（最开始就没注意，导致绕了很久）
第二要理解到双端队列其实也是一个动态的滑动窗口！
剖析细节：
res为存放结果的数组，为什么容量为nums的长度-k+1，用图模拟如下：
为什么用deque.peek() == i- k;当作条件来判断它是否超过生命周期？
要知道是deque.peek() 是当前双端队列中的头（最左边），上述也说了双端队列的头（最左边）是存放的最大元素下标，当遍历到 i 时，当前位置 i 减去窗口容量 k 都还等于双端队列的头部存放的下标，说明已经超过了生命周期，删除该值。
要手动模拟才能深入理解！
为什么要当 i >= k-1时才开始存放结果？
因为当移动到 k-1 这个位置时，滑动窗口刚好到达最大容量。
在B站上有一个视频把该题的原理解释的很明白：B站视频链接
在纯文字中，不好描述与解释这个Deque的深刻含义！（抽象为另一个动态的滑动窗口）
时刻回顾~
前 K 个高频元素：力扣题目链接
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
该题先大致理解，后续再对细节进行深入理解，对未接触的知识进行补充
回顾学习优先队列，priorityQueue 的用法 ， 堆排序。
lass Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
} else {
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll()[0];
}
return ret;
}
将频率数组排序，并找到一个阈值，该阈值是第k个高频元素的频率。然后，我们遍历哈希表，将频率大于或等于阈值的元素添加到结果列表中。
今日主要学习了单调栈，单调队列的原理，及其运用。（深刻理解花费了很多时间）
常回顾，多理解~
一声梧叶一声秋，
一点芭蕉一点愁，
三更归梦三更后......
Fighting!
?
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！