In [33]:
from typing import List

滑动窗口均值

In [56]:
class Solution:
    def meanSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """暴力解法O(N*K)
        
        时间复杂度分析:由于每一个输入数组的元素,我们都需要计算它下K个元素的均值,所以时间复杂度为O(N*K),N是输入数组元素个数。
        这种算法效率低下的原因是,窗口每移动一步,总是有K-1个元素被重复计算了两次。overlapping elements: K-1
        """
        result = []
        for i in range(len(nums) - k + 1):
            window_sum = 0.
            for j in range(i, i + k):
                window_sum += nums[j]
            result.append(window_sum / k)
        return result
    
    def meanSlidingWindow1(self, nums: List[int], k: int) -> List[int]:
        """暴力解法O(N*K)
        """
        result = []
        window_sum = 0.
        for i in range(k):
            window_sum += nums[i]
        result.append(window_sum / k)
        for i in range(1, len(nums) - k + 1):
            window_sum = window_sum - nums[i-1] + nums[i+k-1]
            result.append(window_sum / k)
        return result
In [57]:
solution = Solution()
print(solution.meanSlidingWindow(nums=[1, 3, 2, 6, -1, 4, 1, 8, 2], k=5))
print(solution.meanSlidingWindow1(nums=[1, 3, 2, 6, -1, 4, 1, 8, 2], k=5))
[2.2, 2.8, 2.4, 3.6, 2.8]
[2.2, 2.8, 2.4, 3.6, 2.8]

239. 滑动窗口最大值

In [32]:
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """暴力解法O(N*K)
        
        时间复杂度分析:由于每一个输入数组的元素,我们都需要计算它下K个元素中的最大值,所以时间复杂度为O(N*K),N是输入数组元素个数。
        这种算法效率低下的原因是,窗口每移动一步,总是有K-1个元素被重复计算了两次。overlapping elements: K-1
        """
        result = []
        for i in range(len(nums) - k + 1):
            max_ = -float('inf')
            for j in range(i, i + k):
                max_ = max(nums[j], max_)
            result.append(max_)
        return result
In [29]:
solution = Solution()
solution.maxSlidingWindow(nums=[1,3,-1,-3,5,3,6,7], k=3)
Out[29]:
[3, 3, 5, 5, 6, 7]
In [ ]:
 
In [ ]:
 
In [ ]:
 
In [ ]:
 
In [ ]:
 

Comments