+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-04(1)

2019-06(2)

2019-07(2)

2019-08(87)

2019-09(90)

LeetCode 算法题库【239】——滑动窗口最大值

发布于2020-03-31 14:27     阅读(1099)     评论(0)     点赞(17)     收藏(5)


0

1

2

3

4

5

6

7

8

滑动窗口最大值

题目描述:

ti
mu

解题思路:
  • 第一种:暴力法。这个思路就很好理解,从头开始遍历,用切片取每次的k个元素作为滑动窗口然后把最大值直接append给最后需要返回的最大值集合max_number。非常暴力所以速度比较慢。
  • 时间复杂度:O(N)
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        lens = len(nums)
        max_number = []
        if not nums:
            return []
        for i in range(lens - k + 1):
            max_number.append(max(nums[i:i + k]))
        return max_number

1

  • 第二种:双向队列。
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or len(nums) < k or k <= 0:
            return []
        if k == 1:
            return nums
        max_numbers = []
        temp = [0]
        for i in range(len(nums)):
            if i - temp[0] > k - 1:
                temp.pop(0)
            while temp and nums[i] >= nums[temp[-1]]:
                temp.pop()
            if len(temp) < k - 1:
                temp.append(i)
            if i >= k - 1:
                max_numbers.append(nums[temp[0]])
        return max_numbers

2

0

1

2

3

4



所属网站分类: 技术文章 > 博客

作者:智慧星辰

链接: https://www.pythonheidong.com/blog/article/292436/57e0a57f0f5480f043b5/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

17 0
收藏该文
已收藏

评论内容:(最多支持255个字符)