目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

二、解题思路

每次都添加win里的第一个值，因为win的第一个值永远是最大值的索引；

如果当前的值大于nums里win存储的索引就把win里的对应的值一个一个扔了，然后把这个值加在win末尾，如果最大值的索引与当前循环的索引差值大于等于k，说明查看的k长度的窗口与之前的不重合了，即使是最大值也不属于现在查看的k长度的窗口了， 因此要扔掉；

i要从k-1处开始添加答案，因为0到k-1长度为k。

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def maxSlidingWindow(self, nums: list, k: int) -> list:
     
    
   

    

     

    
    

     

       win, ret = [], []
     
    
   

    

     

    
    

     
 for i, v in enumerate(nums):
     
    
   

    

     

    
    

     
 if i >= k and win[0] <= i - k:
     
    
   

    

     

    
    

     

       win.pop(0)
     
    
   

    

     

    
    

     
 while win and nums[win[-1]] <= v:
     
    
   

    

     

    
    

     

       win.pop()
     
    
   

    

     

    
    

     

       win.append(i)
     
    
   

    

     

    
    

     
 if i >= k - 1:
     
    
   

    

     

    
    

     

       ret.append(nums[win[0]])
     
    
   

    

     

    
    

     
 return ret
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       nums = [1,3,-1,-3,5,3,6,7]
     
    
   

    

     

    
    

     

       k = 3
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.maxSlidingWindow(nums, k)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108866457