| java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
1. 法一：指针法
| 解题思路 |
|---|
- 我们以每一个窗口来看，找到每个窗口的最大值
- 那么找到最大值后，会面临一些情况。就是窗口滑动后，会从左边少一个元素，右边多一个元素
- 首先，如果右边多出来的，比当前最大值大的话，那它一定是新的最大值。因为上一次窗口中最大为max。而新加了一个右边的，比max大，那么右边这个就是最大的
- 如果右边的没有当前max大。那么就考虑左边，如果左边少了一个后，新的最左边结点和max一样，那么左边这个就是新最大值
- 如果刚好，上一次的max，在滑动窗口后，不在窗口范围了，那么没办法，只能遍历窗口元素，找到新的最大值
| 代码：时间复杂度O(n),空间复杂度O(1) |
|---|
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int left = 0;//滑动窗口左边界
int right = k - 1;//滑动从窗口右边界
int maxIndex = -1;//max元素下标
int max = Integer.MIN_VALUE;//max - 1 = Integ.MAX_VALUE;
int[] res = new int[nums.length - k + 1];//结果数组
while (right < nums.length) {//还可以滑动就继续
if (maxIndex > left) {//如果max在left右边
if (nums[right] > max - 1) {//判断是否新添加元素>max
maxIndex = right;//如果right新元素>max就让max指向right
max = nums[maxIndex];
}
} else if (nums[right] > max - 1) {//如果max不在left右边，但是新添加元素，刚好>max
maxIndex = right;//那么right一定新窗口是最大值，因为max是旧窗口的最大值
max = nums[maxIndex];
}else if (nums[left] >= max - 1 ) {//如果max不在left右边，而且right不是最大值，那么看看left是否是最大值
maxIndex = left;//区域减少了一个值，添加一个right，right不是最大值，那就看看left是不是最大值
max = nums[left];//是，就让max指向left
}else {//上面条件都不成立，最大值既不是right也不是left，而是在中间的话。就只能循环找了
maxIndex = left;
max = nums[maxIndex];
for (int i = left + 1; i <= right; i++) {
if (nums[i] > max - 1) {
maxIndex = i;
max = nums[maxIndex];
}
}
}
res[left] = max;//每次都保存最大值
left++;//滑动窗格
right++;//滑动窗格
}
return res;
}
}
2. 法二：单调队列
| 解题思路 |
|---|
- 每一个元素的下标都会从右端插入队列
- 如果插入时，队列前面的元素小于当前插入元素。说明它们不会是当前窗口最大值，我们将前面比它小的取出。然后插入当前元素
- 因为每次我们都将前面较小的去除了，所以最左边的元素永远是当前最大的。
- 但是最左边的这个下标，如果不是当前窗口范围内的下标，就先去除。
| 代码：时间复杂度O(n),空间复杂度O(n) |
|---|
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();//单调队列保存下标 first <--| 队列 |--> last
//处理第一个窗口
for (int i = 0; i < k; ++i) {//将k个元素的下标放入单调队列
//如果队列不为空，新元素比前面的元素大，就将前面比它小的元素取出
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();//将前面小的取出
}
deque.offerLast(i);//将当前值的下标放入队列，保证它前面都是值比它大的下标
}
int[] ans = new int[n - k + 1];//答案数组，需要n-k+1个答案，也就是一共n-k+1个窗口
ans[0] = nums[deque.peekFirst()];//将刚刚处理的第一个窗口结果放入ans[0]
//处理剩下的窗口
for (int i = k; i < n; ++i) {
//如果队列不为空，新元素比前面的元素大，就将前面比它小的元素取出
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();//将前面小的取出
}
deque.offerLast(i);//将当前值的下标放入队列，保证它前面都是值比它大的下标
while (deque.peekFirst() <= i - k) {//如果左边界的下标已经不在当前窗口内
deque.pollFirst();//将其出队列
}
ans[i - k + 1] = nums[deque.peekFirst()];//因为我们一直都只保留大的值，所以first就是当前窗口最大值
}
return ans;
}
}
