leetCode-0239_滑动窗口最大值

Posted on | In |

题目描述

英文题目

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[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

Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

中文题目

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。

返回滑动窗口最大值。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: 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

注意：

你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。

解决方法

方法一
  • 描述

大概思路是用双向队列保存数字的下标，遍历整个数组，如果此时队列的首元素是i - k的话，表示此时窗口向右移了一步，则移除队首元素。然后比较队尾元素和将要进来的值，如果小的话就都移除，然后此时我们把队首元素加入结果中即可

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdlib.h>

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    int head = 0;
    int tail = 0;
    
    int *indexs = malloc(sizeof(int) * numsSize);
    int *results = malloc(sizeof(int) * (numsSize - k + 1));
    
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        while (tail > head && nums[i] >= nums[indexs[tail - 1]]) {
            tail--;
        }
        
        indexs[tail++] = i;
        
        if (indexs[head] <= i - k) {
            head++;
        }
        
        if (i >= k - 1) {
            results[count++] = nums[indexs[head]];
        }
    }
    
    *returnSize = count;
    return results;
}

void test()
{
    int nums[8] = { 1,3,-1,-3,5,3,6,7 };
    int k = 3;
    int count = 0;
    int *list = maxSlidingWindow(nums, 8, k, &count);
    for (int i = 0; i < count; i++) {
        printf("%d ",list[i]);
    }
    printf("\n");
}

题目来源

Sliding Window Maximum

滑动窗口最大值