Leetcode 239:滑动窗口最大值(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 239:滑动窗口最大值(超详细的解法!!!)

in leetcode with 0 comment

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 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

注意:

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

进阶:

你能在线性时间复杂度内解决此题吗?

解题思路

这个问题非常简单,直接使用暴力法就可以过。也就是遍历数组nums,取出对应区间的最大值记录即可。

class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = list()
        if not nums:
            return res
        
        for i in range(len(nums)-k+1):
            j = i + k
            res.append(max(nums[i:j]))
        return res

当然这个问题其实就是一个RMQ问题,所以直接套用st算法就可以在O(nlogn)时间内处理这个问题。

接着我们会思考如何在线性时间复杂度内完成这个目标呢?这里有两个提示,一个是线性复杂度,另一个是最大值,所以我们很容易联想到单调栈的内容。怎么做呢?参考单调栈问题总结,我们可以维护一个递减栈(如果栈的长度大于窗口长度的话,栈底元素出栈),这样的话栈底元素一定是窗口中的最大值。其实这里使用的数据结构不是栈,而是双端队列,但是使用了单调栈的思想。

class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums:
            return list()
        
        res, stack = list(), list()
        for i, val in enumerate(nums):
            if i >= k and i - stack[0] >= k:
                stack.pop(0)
            while stack and nums[stack[-1]] < val:
                stack.pop()
               
            stack.append(i)
            if i > k - 2:
                res.append(nums[stack[0]])
           
        return res

这个写法上有很多的讲究,例如我们stack.append是放在res.append的前面,这样就可以保障我们stack不为空,也因此我们需要在第一个判断的位置添加的是>=而不是>

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses