2020-03-30

针对滑动窗口最大值的思考与代码优化239
解题思路，单调队列。进出队列，就是下标。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if k==1:return nums
        from collections import deque
        d=deque()
        
        for a in range(k):
            while len(d)>0 and nums[a]>nums[d[-1]]:
                d.pop()
            d.append(a)   
        ans=[nums[d[0]]]

        for i in range(k,len(nums)):
            while len(d)>0 and nums[i]> nums[d[-1]]:
                d.pop()
            d.append(i)
            if i-d[0]==k:d.popleft()
            ans.append(nums[d[0]])
            #if i>k-2:ans.append(nums[d[0]])
        return ans

当时，想建立队列，单独提出来，以免当两个for 合并时，需要在最后，加一次 if 的check。
但是，明显看到代码是冗余的，
还是决定合并，想到了列表的切片，测试结果最好64ms。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if k==1:return nums
        from collections import deque
        d,ans=deque(),[]
        for i in range(0,len(nums)):          #write the zero for check
            while len(d)>0 and nums[i]> nums[d[-1]]:
                d.pop()
            d.append(i)
            if i-d[0]==k:d.popleft()
            #O(N)  check
            #if i>k-2:ans.append(nums[d[0]])
            #return ans

             ##ans.append(nums[d[0]])
            ans.append(nums[d[0]])
        return ans[k-1:]

优化，一般来自，再看看，先爬，后站，再跑。