美文网首页
LeetCode - 239. 滑动窗口最大值

LeetCode - 239. 滑动窗口最大值

作者: huxq_coder | 来源:发表于2020-09-01 09:15 被阅读0次

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

    提示:

    1 <= nums.length <= 10^5
    -10^4 <= nums[i] <= 10^4
    1 <= k <= nums.length

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/sliding-window-maximum
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    算法
    swift

    /**
     暴力解法
     外层循环数组,内层循环窗口k,找到最大值
     时间复杂度为O(n*k)
     空间复杂度为O(1)
     提交LeetCode超时
     */
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        // 过滤边界
        guard nums.count > 0 else {
            return []
        }
        var results = [Int]()
        for i in 0..<nums.count-k+1 {
            var maxValue = nums[i]
            for j in 1..<k {
                maxValue = max(maxValue, nums[i+j])
            }
            results.append(maxValue)
        }
        return results
    }
    
    
    
    /**
     双端队列
     单调递减队列,保证队列头部始终是最大值
     尾部插入数据,判断当前索引值 ? 尾部索引值,小于:尾插;否则,移除尾部数据
     判断队列内的元素个数是否超出窗口k, 当前索引 - 队列头部索引 ?k 超出,移除队列头部
    参考题解:https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/
     时间复杂度为O(n)
     空间复杂度为O(n)
     */
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        // 过滤边界
        guard nums.count > 0 else {
            return []
        }
        var results = [Int](repeating: 0, count: nums.count-k+1)
        // 双端队列,单调递减,保证头部为最大值
        var deque = [Int]()
        var currentIndex = 0
        for i in 0..<nums.count {
            // 当前索引值 大于等于 队列尾部的值,移除尾部索引
            while !deque.isEmpty && nums[i] >= nums[deque.last!]  {
                deque.removeLast()
            }
            deque.append(i)
            // 队列头部的索引超出当前窗口,移除头部索引
            while deque.first! <= i - k {
                deque.removeFirst()
            }
            // 数组索引小于 k-1 的元素不需要保存记录
            if i >= k - 1 {
                results[currentIndex] = nums[deque.first!]
                currentIndex += 1
            }
        }
        return results
    }
    

    GitHub:https://github.com/huxq-coder/LeetCode

    相关文章

      网友评论

          本文标题:LeetCode - 239. 滑动窗口最大值

          本文链接:https://www.haomeiwen.com/subject/ukvmsktx.html