滑动窗口

more

剑指 Offer II 041. 滑动窗口的平均值

描述

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。

实现 MovingAverage 类：

• MovingAverage(int size) 用窗口大小 size 初始化对象。
• double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。

实例：

输入：
inputs = ["MovingAverage", "next", "next", "next", "next"]
inputs = [[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]

解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3

解法

python版

class MovingAverage:
    '''
    暴力方法
    '''
    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """
        self.store = list()
        self.size = size


    def next(self, val: int) -> float:
        # 每次取后三个
        self.store.append(val)
        # cur_size = len(self.store)
        temp = self.store[::-1][:self.size]
        cur_len = len(temp)
        return sum(temp)/cur_len

java版

class MovingAverage {
    private Queue<Integer> queue;
    private int size;
    private double sum;

    public MovingAverage(int size){
        queue = new LinkedList();
        this.size = size;
        sum = 0;
    }
    public double next(int val){

        sum += val; // TODO 计算累加和
        // 如果队列的容量达到的滑动窗口的最大值，则将最老的元素出队
        if(queue.size() == size){
            sum -= queue.poll();
        }
        queue.offer(val); // 新元素入队
        return sum / queue.size();
    }
}

剑指 Offer 59 - I. 滑动窗口的最大值

与239. 滑动窗口最大值相同

描述

给定一个数组 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

解法：python

在239中会超时

class Solution:
    def maxSlidingWindow(self, nums: list, k: int) -> list:

        res = []
        lens = len(nums)
        for i in range(0,lens):
            if i+k > lens:
                continue
            res.append(max(nums[i:i+k]))
            # print(nums[i:i+k])
        return res

解法：优先队列

来自 leetcode官方题解，

对于两个相邻（只差了一个位置）的滑动窗口，他们共用着$k-1$​个元素，而只有1个元素是变化的，可以进行根据这个特点进行优化。

对于最大值，可以使用优先队列（大根堆），可以实时维护一系列元素的最大值。

对于本题，初始时，可以将数组 $nums$ 前$k$个元素放入优先队列中。

每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组$nums$​中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久的从优先队列中移除。

通过不断移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。

为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组（num, index），表示元素 $num$ 在数组中的下标为 $index$。

def maxSlidingWindow2(self, nums: list, k: int) -> list:
    n = len(nums)
    # python默认的优先队列是小根堆，通过添加负号来达到最大值
    q = [(-nums[i],i) for i in range(k)]  # 先保存第一个滑动窗口

    # temp = q[:k]
    # heapq.heapify(temp)
    # print(temp)
    heapq.heapify(q) # 队列转换为堆

    # print(q)
    ans = [-q[0][0]] # 得到堆顶元素

    # 从第k个元素开始
    for i in range(k,n):
        print(i,q)
        heapq.heappush(q,(-nums[i],i)) # 入队 

        while q[0][1] <= i-k:   # i-k 是当前滑动窗口的左边界
            heapq.heappop(q) # 如果它在左边界的外面，说明不在当前滑动窗口，故弹出
        
        ans.append(-q[0][0])
    return ans

主要是通过优先队列来获得当前窗口的最大值，在取当前队头元素时，先判断当前元素是否在窗口内，如果不在窗口内则将其弹出。

while部分的语句判断队头元素是不是当前窗口的，i-k得到的是前一个窗口的开始位置。

解法：单调队列

由于我们需要求的是滑动窗口的最大值，如果当前滑动窗口中有两个下标 $i$ 和 $j$，其中 $i$ 在 $j$ 的左侧（$i<j$），并且 $i$ 对应的元素不大于 $j$ 对应的元素 ($nums[i]\leq nums[j]$)，那会发生什么呢？

当滑动窗口向右移动时，只要 $i$ 还在窗口，那么 $j$ 一定也还在窗口中，这是 $i$ 在 $j$ 的左侧保证的。因此，由于$nums[j]$ 的存在，$nums[i] $ 一定不会是滑动窗口中的最大值了，我们可以将 $nums[i]$ 永久地移除。

因此可以用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组$nums$​​中对应的值是严格单调递减的。

这里是为了让队头元素是最大值

因为如果队列中有两个相邻的下标，它们对应的值相等或者递增，那么令前者为 $i$ ，后者为 $j$ ，就对应了上面所说的情况，既 $nums[i]$​ 会被移除，这就产生了矛盾。

当前滑动窗口不断向右移动时，我们需要把一个新的元素放入队列中。为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果前者大于等于后者，那么队尾的元素就可以永久地被移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾元素。

由于队列中的下标对应的元素是单独递减的，因此此时队首下标对应的元素就是滑动窗口中的最大值。

但与方法一相同的是，此时的最大值可能在滑动窗口左边界的左侧，并且随着窗口向右移动，它永远不可能出现在滑动窗口中了。因此我们还需要不断从队首弹出元素，直到队首元素在窗口中为止。

为了可以同时弹出队首和队尾元素，我们需要使用双端队列。满足这种单调性的双端队列一般称作【单调队列】。