add 1 leetcodes

Jack-Lee-Hiter · Jack-Lee-Hiter · commit 16a250a25c14 · 2016-08-27T16:14:46.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/Target Offer/&#28369;&#21160;&#31383;&#21475;&#30340;&#26368;&#22823;&#20540;.py b/Target Offer/&#28369;&#21160;&#31383;&#21475;&#30340;&#26368;&#22823;&#20540;.py
@@ -9,7 +9,7 @@
 # -*- coding:utf-8 -*-
 class Solution:
     def maxInWindows(self, num, size):
-        if num == None or len(num) <= 0 or size <= 0:
+        if not num or size <= 0:
             return []
         deque = []
         if len(num) >= size:
diff --git a/leetcode/239. Sliding Window Maximum.py b/leetcode/239. Sliding Window Maximum.py
@@ -0,0 +1,39 @@
+'''
+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.
+
+For example,
+Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
+
+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
+Therefore, return the max sliding window as [3,3,5,5,6,7].
+'''
+class Solution(object):
+    def maxSlidingWindow(self, nums, k):
+        if not nums or k <= 0:
+            return []
+        '''
+        if you want to modify time complexity, you can write below:
+        from collections import deque
+        res, queue = [], deque()
+        and replace queue.pop(0) with queue.popleft()
+        '''
+        res, queue = [], []
+        for ind, val in enumerate(nums):
+            if queue and queue[0] <= ind - k:
+                queue.pop(0)
+            while queue and nums[queue[-1]] < val:
+                queue.pop()
+            queue.append(ind)
+            if ind + 1 >= k:
+                res.append(nums[queue[0]])
+        return res
+
+s = Solution()
+print(s.maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
