leetcode239 -- Sliding Window Maximum(就是maxpooling一维的那个)

leetcode239 -- Sliding Window Maximum(就是maxpooling一维的那个)

题目


Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[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

Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

解答O(n)

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        
        
        ret = []
        if len(nums)<k or k==0:
            return []
        queue = []
        data = nums
        for i in range(k):
            while len(queue)>0 and data[i]>=data[queue[-1]]:
                del(queue[-1])
                
            queue.append(i)
        for i in range(k, len(data)):
           
            ret.append(data[queue[0]])
            
            while len(queue)>0 and data[i]>= data[queue[-1]]:
                del(queue[-1])
            queue.append(i)
                
            if len(queue)>0 and i-queue[0]>=k:
                del(queue[0])
             
        ret.append(data[queue[0]])
        
        return ret 
    

def mapooling(data,k):
    ret = []

    if len(data) ==0 or k<=0 or len(data)<k:
        return ret

    queue = []

    for i in range(len(data)):
        if len(queue)>0:
            # 先决定什么时候出队
            if i-queue[0] >=k:   # 这时候指的是如果窗口的长度已经大于k了,说明这时候首元素已经没有用了.
                del(queue[0])

            while len(queue)>0 and data[i] >= data[queue[-1]]:   # 因为这时候队列的最后一个元素不是最大值
                del(queue[-1])

        queue.append(i)

        if i+1>=k:   # 如果当前遍历的长度已经过了窗口的长度了就可以存结果了.
            ret.append(data[queue[0]])

    return ret

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦