跳转至

239. 滑动窗口最大值

最后更新：2024-05-10-22

链接：https://leetcode.cn/problems/sliding-window-maximum/description/

题目描述

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

返回 滑动窗口中的最大值 。

题目示例

输入： nums = [1,3,-1,-3,5,3,6,7], k = 3

输出： [3,3,5,5,6,7]

解释：

Text Only
1
2
3
4
5
6
7
8
滑动窗口的位置                 最大值   
---------------               -----  
[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

输入： nums = [1], k = 1

输出： [1]

提示：

  • \(1 <= nums.length <= 10^5\)
  • \(-10^4 <= nums[i] <= 10^4\)
  • \(1 <= k <= nums.length\)

解题思路

使用快速排序，暴力顺序判断边界值，可能会超时

以示例1为例

  1. numsSize <= K的情况，直接快速排序，降序，然后返回nums[0]就可以
  2. 下标从1开始

过程示例

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
滑动窗口的位置                          最大值   
---------------                         -----   
[1  3  -1] -3  5  3  6  2  1  2  7       3   
1 [3  -1  -3] 5  3  6  2  1  2  7        3   
1  3 [-1  -3  5] 3  6  2  1  2  7        5   
1  3  -1 [-3  5  3] 6  2  1  2  7        5   
1  3  -1  -3 [5  3  6] 2  1  2  7        6   
1  3  -1  -3  5 [3  6  2] 1  2  7        6   
1  3  -1  -3  5  3 [6  2  1] 2  7        6   
1  3  -1  -3  5  3  6 [2  1  2] 7        2   
1  3  -1  -3  5  3  6  2 [1  2  7]       7

每次的滑动，都是前面少了一个值a，后面多了一个值b；

我们假设以值a开始的区间，最大值为maxa；

那么必然有条件：

Text Only
1
2
3
4
5
6
7
8
9
1.max[a] = a，说明从a + 1到a + k - 1这 k - 1个数据，都是小于a的；

    - 如果b > a, 那么新的区间，b肯定是最大值
    - 如果b < a, 那么新的区间，我们需要重新获取最大值

2.max[a] != a，那么maxa肯定是在 a + 1 到 b 这k个数字中.

    - 如果 b > a, 那么新的区间，最大值肯定是b
    - 如果 b < a, 那么新的区间，最大值肯定是a

综上，我们需要做的处理是：

Text Only
1
2
3
1. 如果b > a, 新区间max[a + 1] = b;
2. 否则，如果max[a] = a， 新的区间重新计算最大值
3. 否则，新的区间max[a + 1] = max[a];
C
 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
* Note: The returned array must be malloced, assume caller calls free().
*/

#define MAX_NUMS_LEN 100000

int getmax(int a, int b)
{
    if (a > b) {
        return a;
    }
    return b;
}

int comp(const void *a, const void *b)
{
    if (*(int*)a < *(int*)b) {
        return 1;
    }

    return -1;
}

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize)
{
    int *result = NULL;
    int i;
    int tmp[MAX_NUMS_LEN] = {0};

    if (k == 1) {
        *returnSize = numsSize;
        return nums;
    }

    result = (int*)malloc(sizeof(int) * MAX_NUMS_LEN);
    (void)memset(result, 0, sizeof(int) * MAX_NUMS_LEN);
    if (numsSize <= k) {
        *returnSize = 1;
        qsort(nums, numsSize, sizeof(int), comp);
        result[0] = nums[0];
        return result;
    }

    for (i = 0; i < k; i++) {
        result[0] = getmax(result[0], nums[i]);
    }

    *returnSize = numsSize - k + 1;
    for (i = 1; i < *returnSize; i++) {
        // printf("%d nums[%d] : %d, nums[%d] : %d, \n", i, i - 1, nums[i - 1], i, nums[i]);
        // 新加进来的值比前面的最大值还大，因为前面的排序之后最大值是result[i - 1]，所以新加进来的值就是当前区域的最大值
        if (nums[i + k - 1] >= result[i - 1]) {
            result[i] = nums[i + k - 1];
        } else if (nums[i - 1] == result[i - 1]) {
            // 上一个值就是上个区间的最大值，需要重新获取当前为起点的区间的最大值
            (void)memset(tmp, 0, sizeof(int) * MAX_NUMS_LEN);
            memcpy(tmp, &nums[i], k * sizeof(int));
            // printf("2  tmp[0] : %d, tmp[1] : %d, tmp[2] : %d\n", tmp[0], tmp[1], tmp[2]);
            qsort(tmp, k, sizeof(int), comp);
            result[i] = tmp[0];
        } else {
            // 新加进来的nums[i + k - 1]比result[i - 1]小，并且减出去的值不是上一个区间的最大值
            // 说明当前区间的最大值还在，直接赋值即可
            result[i] = result[i - 1];
        }
        // printf("3  result[%d] : %d\n", i, result[i]);
    }

    return result;
}
C
 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
void swap(int** a, int** b) {
    int* tmp = *a;
    *a = *b, *b = tmp;
}

int cmp(int* a, int* b) {
    return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
}

struct Heap {
    int** heap;
    int size;
    int capacity;
};

void init(struct Heap* obj, int capacity) {
    obj->size = 0;
    obj->heap = NULL;
    obj->capacity = capacity;
    obj->heap = malloc(sizeof(int*) * (obj->capacity + 1));
    for (int i = 1; i <= obj->capacity; i++) {
        obj->heap[i] = malloc(sizeof(int) * 2);
    }
}

void setFree(struct Heap* obj) {
    for (int i = 1; i <= obj->capacity; i++) {
        free(obj->heap[i]);
    }
    free(obj->heap);
    free(obj);
}

void push(struct Heap* obj, int num0, int num1) {
    int sub1 = ++(obj->size), sub2 = sub1 >> 1;
    (obj->heap[sub1])[0] = num0, (obj->heap[sub1])[1] = num1;
    while (sub2 > 0 && cmp(obj->heap[sub2], obj->heap[sub1]) < 0) {
        swap(&(obj->heap[sub1]), &(obj->heap[sub2]));
        sub1 = sub2, sub2 = sub1 >> 1;
    }
}

void pop(struct Heap* obj) {
    int sub = 1;
    swap(&(obj->heap[sub]), &(obj->heap[(obj->size)--]));
    while (sub <= obj->size) {
        int sub1 = sub << 1, sub2 = sub << 1 | 1;
        int maxSub = sub;
        if (sub1 <= obj->size && cmp(obj->heap[maxSub], obj->heap[sub1]) < 0) {
            maxSub = sub1;
        }
        if (sub2 <= obj->size && cmp(obj->heap[maxSub], obj->heap[sub2]) < 0) {
            maxSub = sub2;
        }
        if (sub == maxSub) {
            break;
        }
        swap(&(obj->heap[sub]), &(obj->heap[maxSub]));
        sub = maxSub;
    }
}

int* top(struct Heap* obj) {
    return obj->heap[1];
}

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    struct Heap* q = malloc(sizeof(struct Heap));
    init(q, numsSize);
    for (int i = 0; i < k; i++) {
        push(q, nums[i], i);
    }
    int* ans = malloc(sizeof(int) * (numsSize - k + 1));
    *returnSize = 0;
    ans[(*returnSize)++] = top(q)[0];

    for (int i = k; i < numsSize; ++i) {
        push(q, nums[i], i);
        while (top(q)[1] <= i - k) {
            pop(q);
        }
        ans[(*returnSize)++] = top(q)[0];
    }
    setFree(q);
    return ans;
}

超时了

Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Note: The returned array must be malloced, assume caller calls free().
*/

func maxSlidingWindow(nums []int, k int) []int {
    var lenInput = len(nums)
    if (lenInput == 1) || (k == 1) {
	    return nums
    }

    result := make([]int, lenInput-k+1)
    for i := 0; i <= lenInput-k; i++ {
	    numTmp := make([]int, k)
	    // fmt.Printf("numTmp %v, nums %v\n", numTmp, nums)
	    copy(numTmp, nums[i:i+k])
	    sort.Ints(numTmp)
	    // fmt.Printf("numTmp %v, nums %v\n", numTmp, nums)
	    result[i] = numTmp[k-1]
    }

    // fmt.Printf("%v\n", result)
    return result
}