[关闭]
@liweiwei1419 2019-05-24T05:29:04.000000Z 字数 1532 阅读 1343

LeetCode 第 239 题:滑动窗口的最大值

滑动窗口 索引数组


传送门:滑动窗口最大值

要求:给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。

返回滑动窗口最大值。

示例:

  1. 输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
  2. 输出: [3,3,5,5,6,7]
  3. 解释:
  4. 滑动窗口的位置 最大值
  5. --------------- -----
  6. [1 3 -1] -3 5 3 6 7 3
  7. 1 [3 -1 -3] 5 3 6 7 3
  8. 1 3 [-1 -3 5] 3 6 7 5
  9. 1 3 -1 [-3 5 3] 6 7 5
  10. 1 3 -1 -3 [5 3 6] 7 6
  11. 1 3 -1 -3 5 [3 6 7] 7

注意:

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

进阶:

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

分析:

《剑指 Offer (第 2 版)》第 59 题:滑动窗口的最大值-1

关键:

1、如果后进来一个数,前面的元素比它小,那么前面的元素就永远不可能是“滑动窗口中的最大值”

2、如果判断当前“滑动窗口中的最大值”应该被移除掉,所以“滑动窗口”中应该保存的是下标。

直接给出最佳解法:

《剑指 Offer (第 2 版)》第 59 题:滑动窗口的最大值-2

思考:为什么要存的是下标,因为要判断当前“滑动窗口”的最大值是否被滑出边界。

  1. # 同 LeetCode 第 239 题,传送门:滑动窗口最大值。
  2. class Solution:
  3. def maxSlidingWindow(self, nums, k):
  4. """
  5. :type nums: List[int]
  6. :type k: int
  7. :rtype: List[int]
  8. """
  9. # 关键:如果后进来一个数,前面的元素比它小
  10. # 那么前面的元素就永远不可能是"滑动窗口中的最大值"
  11. l = len(nums)
  12. if l == 0 or k <= 0:
  13. return []
  14. res = []
  15. window = []
  16. for i in range(l):
  17. # 考虑什么时候,要把最大移除
  18. # 左边界划出的时候,应该是 window.pop(0)
  19. # [0,1,2,3,4]
  20. # [ i]
  21. # window[0] == i - k 这个条件特别容易忽略
  22. # 这一步条件特别重要:只有当当前最大元素刚刚滑出“滑动窗口”时,才可以把 window[0] 去掉
  23. if i >= k and window[0] == i - k:
  24. window.pop(0)
  25. # 考虑把不可能是最大的元素全部 kill 掉
  26. while window and nums[i] >= nums[window[-1]]:
  27. window.pop()
  28. window.append(i)
  29. # 什么时候有滑动窗口呢?
  30. if i >= k - 1:
  31. res.append(nums[window[0]])
  32. return res
  33. if __name__ == '__main__':
  34. nums = [1, 3, -1, -3, 5, 3, 6, 7]
  35. k = 3
  36. solution = Solution()
  37. result = solution.maxSlidingWindow(nums, k)
  38. print(result)

总结:

1、整个过程中,保持 windows[0] 对应的下标就是滑动窗口的最大值。

覃超给的解法:

1、使用大顶堆,但是要使用索引堆。维护这个堆的元素固定,维护堆顶元素是堆中最大的,时间复杂度:

2、使用双端队列:时间复杂度 。下面这个版本的写法是最优解:多写几遍就能理解。说明:window 中存储的是下标。

《剑指 Offer (第 2 版)》第 59 题:滑动窗口的最大值-3

说明:window[0] <= i-k 应该是 i-k ,表示,此时滑动窗口中最大的那个元素正好滑出“滑动窗口”了。

具体例子:

数值 1 3 -1 -3 5 3 6
索引 0 1 2 3 4 5 6

如果遍历的指针 i 在 那个位置上,滑动窗口的长度是 ,此时索引 就应该是第 1 个滑出“滑动窗口”的元素

其它解法:两个 for 循环,第一个 for 循环滑动窗口,第二个 for 循环滑动窗口中的值,寻找最大值。还可以使用时间复杂度更低的双端队列求解。

Java 写法:

《剑指 Offer (第 2 版)》第 59 题:滑动窗口的最大值-4
(本节完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注