文章目录
一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
- 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
五【题目示例】
- 示例:
输入: 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 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
六【题目提示】
七【解题思路】
- 维护单调队列，队列中存放数组下标，存放当前窗口的最大值的下标，for循环里面分四步，第一步就是判断当前窗口的长度是否超过了k，如果超过了就将队列头元素poll出，第二步最重要，判断当前位置元素和队列中最小的元素谁大，如果当前元素大就将小的出队列，如果队列中的元素大，说明当前窗口最大值不变，第三步将当前元素下标加入队列中，保持队列元素单调递减，最后一步将每一步的滑动窗口的最大值加入到结果数组中
八【时间频度】
九【代码实现】
- Java语言版
package Queue;
import java.util.Arrays;
import java.util.LinkedList;
public class o59_I_SlidingWindowMaximum {
public static void main(String[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] res = maxSlidingWindow(nums, k);
System.out.println("res = " + Arrays.toString(res));
}
public static int[] maxSlidingWindow(int[] nums, int k) {
// 如果列表为空直接返回
if (nums.length == 0) {
return nums;
}
// 定义队列
LinkedList<Integer> queue = new LinkedList<>();
// 定义结果数组
int[] res = new int[nums.length - k + 1];
// 定义结果数组下标
int index = 0;
// 开始循环
for (int i = 0; i < nums.length; i++) {
// 因为我们要维护这个队列里面的数据是从大到小的，所以如果队列最后一个元素小于等于数组当前值，那么弹出队列最后一个元素，加入新元素
while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
queue.pollLast();
}
// 下面就把数组当前值加入到队列最后面，顺序仍然是从大到小
queue.addLast(i);
// 如果窗口已经划过了队列头部的元素，那么这个元素用不到，需要把后面的元素“升级”，就将头元素弹出队列
if (queue.peekFirst() == i - k) {
queue.pollFirst();
}
// 如果达到一个窗口大小，那么结果数组就加入当前队列最大值，除了第一次需要等三个值为一个窗口，后面进来一个值就能形成一个窗口
if (i >= (k - 1)) {
res[index++] = nums[queue.peekFirst()];
}
}
return res;
}
}
- C语言版
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize)
{
/*如果数组为空直接返回*/
if (numsSize == 0)
{
*returnSize = 0;
return nums;
}
/*定义队列*/
int* queue = (int *)malloc(numsSize * sizeof(int));
/*定义结果数组*/
int* res = (int *)malloc(numsSize * sizeof(int));
/*头指针*/
int front = 0;
/*尾指针*/
int rear = 0;
/*定义结果数组下标*/
int index = 0;
/*开始循环*/
for (int i = 0; i < numsSize; i++)
{
/*因为我们要维护这个队列里面的数据是从大到小的，所以如果队列最后一个元素小于等于数组当前值，那么弹出队列最后一个元素，加入新元素*/
while (front < rear && nums[queue[rear - 1]] <= nums[i]);
{
rear--;
}
/*下面就把数组当前值加入到队列最后面，顺序仍然是从大到小*/
queue[rear++] = i;
/*如果窗口已经划过了队列头部的元素，那么这个元素用不到，需要把后面的元素“升级”，就将头元素弹出队列*/
if (queue[front] == i - k)
{
front++;
}
/*如果达到一个窗口大小，那么结果数组就加入当前队列最大值，除了第一次需要等三个值为一个窗口，后面进来一个值就能形成一个窗口*/
if (i >= k - 1)
{
res[index++] = nums[queue[front]];
}
}
/*返回结果*/
*returnSize = index;
return res;
}
十【提交结果】
- Java语言版
- C语言版
