数据结构-滑动窗口问题

Posted on | Post modified: | In
Words count in article: 1.7k

原始问题分析

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
常规解法：时间复杂度为$O(N * w)$，也就是每次对一个窗口都需要遍历其中的 w 个数，选出最大值。

$O(N)$解法：准备一个双端队列，双端队列存放着数组中的下标值。假设当前为 arr[i]，则放入规则如下：
left 和 right 指针都只会向右移动，不会回退。

  • right 右滑，窗口加数：
    1）如果 queue 为空，直接把下标 i 放入 queue 中；
    2）如果 queue 不为空，取出当前 queue 队尾存放的下标 j。如果 arr[j] > arr[i]，则直接把 i 放入队尾；
    3）如果 arr[j] <= arr[i]，则一直从 queue 的队尾弹出下标，直到某个下标在 queue 中的对应值大于 arr[i]，然后把 i 放入队尾 【为什么可以弹出，因为我永远比你晚过期，我又比你大或者和你一样大，有我在，你永远不可能最大，所以你可以弹出了】
  • left 右滑，窗口减数：
    1）看弹出的 left 是否与队列头相等，如果相等，说明这个队列头已经不在窗口内了，所以弹出 queue 当前的队首元素 。

双端队列的队头就是当前窗口最大值的下标。

应用

上面的滑动窗口的实现是通用结构，即 left 和 right 指针随便往右移，而在实际解题过程在，都是会限制窗口的大小。

1. 剑指offer：滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

常规解法：
时间复杂度为O(N * w)，也就是每次对一个窗口都需要遍历其中的 w 个数，选出最大值。

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
# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if len(num) < size or size == 0:
            return []
        # left, right = 0, size-1
        # res = []
        # while right < len(num):
        #     maxindex = left
        #     for j in range(left+1,right+1):
        #         if num[j] > num[maxindex]:
        #             maxindex = j
        #     res.append(num[maxindex])
        #     left += 1
        #     right += 1
        # return res
        res = []
        for i in range(len(num)-size+1):
            res.append(max(num[i:i+size]))
        return res

if __name__ == '__main__':
    result = Solution().maxInWindows([2,3,4,2,6,2,5,1],3)
    print(result)

$O(N)$解法：
和通用结构相比。只在弹出时稍微改变：
如果queue对应的下标等于i-size, 说明当前队首下标已经过期，则弹出queue当前队首下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import deque
# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if len(num) < size or size == 0:
            return []
        res = [0] * (len(num)-size+1)
        index = 0
        queue = deque()
        for i in range(len(num)):
            while len(queue) != 0 and num[queue[-1]] <= num[i]:
                queue.pop()
            queue.append(i)
            if queue[0] == i-size:
                queue.popleft()
            if i >= size-1:  # 有窗口形成后，在计算窗口内最大值
                res[index] = num[queue[0]]
                index += 1
        return res

2. 最大值减去最小值小于或等于num的子数组数量

给定数组arr和整数num，返回有多少个子数组满足如下情况:

$max(arr[i:j]) - min(arr[i:j]) <= num$

$max(arr[i:j])$表示子数组$arr[i:j]$中的最大值，$min(arr[i:j])$表示子数组$arr[i:j]$中的最小值。

要求：如果数组长度为 N，请实现时间复杂度为 O(N)的解法。

解题思路

子数组的数量：
以0开始：0~0，0~1，...，0~N-1，共N种情况；
以1开始：1~1，1~2，...，1~N-1，共N-1种情况；
……
以N-1开始：N-1~N-1，共1种情况。
所以总共有 $N+N-1+N-2+…+2+1=\frac{N(N-1)}{2}$种情况。

暴力解法：
两层遍历所有情况，一层遍历求最大最小值，共三层遍历，时间复杂度$O(N^3)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding:utf-8 -*-
class Solution:
    def main(self, arr, num):
        # write code here

        res = 0
        for start in range(len(arr)):
            for end in range(start, len(arr)):
                if self.isValid(arr, start, end, num):
                    res += 1
        return res

    def isValid(self, arr, start, end , num):
        max_value = float('-inf')
        min_value = float('inf')
        for i in range(start, end+1):
            max_value = max(max_value, arr[i])
            min_value = min(min_value, arr[i])
        return max_value-min_value <= num


if __name__ == '__main__':
    result = Solution().main([1,3,5,7,9,11,13,15],4)
    print(result)

$O(N)$解法：

两个结论：

  • 如果子数组arr[i:j]满足条件，那么arr[k:l]（i<=k<=l<=j）一定满足条件，即若一个数组满足条件，它的所有子数组肯定满足条件，因为[max 变小 - min 变大 <= num 肯定成立]。
  • 如果子数组 arr[i:j] 不满足条件，那么 arr[k:l] （k <= i，I >= j） 都不满足条件，即若一个数组不满足条件，所有包含它的数组肯定都不满足条件。因为[max变大 - min变小 >= num肯定成立]。

步骤：
准备两个双端队列，一个 maxQueue 是窗口内最大值更新结构，一个 minQueue 是窗口内最小值更新结构，left、right 表示窗口的左右边，窗口范围为 [left , right - 1]；算以 left 开头达标的子数组个数，每个 left 就可以算出一批答案，相加即可。

  • 1)以 left 开头的情况下，right 往外扩，扩到不达标就停【因为再往外肯定也不达标】，算以 left 开头的子数组有多少个【这些子数组都达标的】；
  • 2)left 右移一位，然后重复 1）。

因为 left，right 都不后退，且每个数都只进出一次，所以时间复杂度是 $O(N)$。

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
from collections import deque
# -*- coding:utf-8 -*-
class Solution:
    def main(self, arr, num):
        # write code here

        maxQueue = deque()
        minQueue = deque()
        left, right = 0, 0
        res = 0
        while left < len(arr):
            while right < len(arr):

                while len(maxQueue) != 0 and arr[maxQueue[-1]] <= arr[right]:
                    maxQueue.pop()
                maxQueue.append(right)

                while len(minQueue) != 0 and arr[minQueue[-1]] >= arr[right]:
                    minQueue.pop()
                minQueue.append(right)

                if arr[maxQueue[0]] - arr[minQueue[0]] > num: # 不满足
                    break

                right += 1

            # left向前推动， 两个双端队列调整
            if maxQueue[0] == left:
                maxQueue.popleft()
            if minQueue[0] == left:
                minQueue.popleft()

            res += right - left # 收集满足的结果
            left += 1 # 下一个开头
            
        return res
    
if __name__ == '__main__':
    result = Solution().main([1,3,5,7,9,11,13,15],4)
    print(result)

参考文献：
https://blog.csdn.net/pcwl1206/article/details/96431668
https://www.cnblogs.com/xieyupeng/p/10373585.html

Donate comment here
------------The End------------
0%