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 knumbers 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].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
这是一道非常有意思的题目。首先思路非常多，可以利用的数据结构也很多。
首先考虑暴力解法。即对每个sliding window都求最大值，复杂度为O(nk)。
下面考虑优化，对于求最大值，最小值，有一个非常好的数据结构，就是堆，这里需要在移动窗口的时候删除元素，如果用普通堆来做删除的复杂度为O(n)。显然不合适。这时候hashheap就可以派上用场，O(logk)时间求最大值，O(logk)时间删除元素。复杂度为O(nlogk)。空间复杂度为O(k)。代码如下：
class Solution:
"""
@param nums: A list of integers.
@return: The maximum number inside the window at each moving.
"""
def maxSlidingWindow(self, nums, k):
if not nums or len(nums) < k:
return []
res = []
heap = HashHeap('max')
for i in xrange(k):
heap.add(nums[i])
for i in xrange(k, len(nums)):
res.append(heap.top())
heap.delete(nums[i - k])
heap.add(nums[i])
res.append(heap.top())
return res
class Node(object):
"""
the type of class stored in the hashmap, in case there are many same heights
in the heap, maintain the number
"""
def __init__(self, id, num):
self.id = id #id means its id in heap array
self.num = num #number of same value in this id
class HashHeap(object):
def __init__(self, mode):
self.heap = []
self.mode = mode
self.size = 0
self.hash = {}
def top(self):
return self.heap[0] if len(self.heap) > 0 else 0
def contain(self, now):
if self.hash.get(now):
return True
else:
return False
def isempty(self):
return len(self.heap) == 0
def _comparesmall(self, a, b): #compare function in different mode
if a <= b:
if self.mode == 'min':
return True
else:
return False
else:
if self.mode == 'min':
return False
else:
return True
def _swap(self, idA, idB): #swap two values in heap, we also need to change
valA = self.heap[idA]
valB = self.heap[idB]
numA = self.hash[valA].num
numB = self.hash[valB].num
self.hash[valB] = Node(idA, numB)
self.hash[valA] = Node(idB, numA)
self.heap[idA], self.heap[idB] = self.heap[idB], self.heap[idA]
def add(self, now): #the key, height in this place
self.size += 1
if self.hash.get(now):
hashnow = self.hash[now]
self.hash[now] = Node(hashnow.id, hashnow.num + 1)
else:
self.heap.append(now)
self.hash[now] = Node(len(self.heap) - 1,1)
self._siftup(len(self.heap) - 1)
def pop(self): #pop the top of heap
self.size -= 1
now = self.heap[0]
hashnow = self.hash[now]
num = hashnow.num
if num == 1:
self._swap(0, len(self.heap) - 1)
self.hash.pop(now)
self.heap.pop()
self._siftdown(0)
else:
self.hash[now] = Node(0, num - 1)
return now
def delete(self, now):
self.size -= 1
hashnow = self.hash[now]
id = hashnow.id
num = hashnow.num
if num == 1:
self._swap(id, len(self.heap)-1) #like the common delete operation
self.hash.pop(now)
self.heap.pop()
if len(self.heap) > id:
self._siftup(id)
self._siftdown(id)
else:
self.hash[now] = Node(id, num - 1)
def parent(self, id):
if id == 0:
return -1
return (id - 1) / 2
def _siftup(self,id):
while abs(id -1)/2 < id : #iterative version
parentId = (id - 1)/2
if self._comparesmall(self.heap[parentId],self.heap[id]):
break
else:
self._swap(id, parentId)
id = parentId
def _siftdown(self, id): #iterative version
while 2*id + 1 < len(self.heap):
l = 2*id + 1
r = l + 1
small = id
if self._comparesmall(self.heap[l], self.heap[id]):
small = l
if r < len(self.heap) and self._comparesmall(self.heap[r], self.heap[small]):
small = r
if small != id:
self._swap(id, small)
else:
break
id = small
继续考虑是否可以优化，题目提示能否线性时间解决，其实这就比较tricky了，甚至提示使用deque，我也没有想出特别好的对策。其实这题应该想到对于这种求最大值的题目，单调队列是一个很好的选择，和单调栈类似，单调队列还有一个比较好的功能是：可以从头部删除元素，也就是对于过期的头部元素，可以比较及时的删除。那具体怎么做呢？
是单调递增队列还是单调递减队列？首先我们的元素增加都使从后段增加，队列尾部一般都是新增加的元素，我们无法保证它最大，那么选用单调递减队列，使其
头部是最大元素不失为一个很好的选择，之后我们继续思考，什么情况下进行增删，首先队首元素虽然是最大值，但是如果窗口移动后，它不在窗口内，则需要删除这个元素，每次窗口只移动一格，所以每次最多删除一个元素。另外我们每次增加新元素时，如果队列里有比它小的历史元素时，则这些元素本身不再有可能成为最大值，所以删除它们保持队列的单调递减性。单调栈和单调队列都有一个地方需要注意，就是相等时如何操作，如果队列里有元素和当前元素相等，我们是否需要删除,思考一下，其实应该删除，对于求最大值的情况，如果i已经进入窗口内，如果i对应的元素是这个窗口的最大值，前面那个和它相等的历史元素也就失效了。
注意和单调栈非常类似，单调队列存的同样是index。空间复杂度O(n),时间复杂度O(n),代码如下：
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or len(nums) < k:
return []
#O(n), deque, you must can
dq = collections.deque()
res = []
for i in xrange(len(nums)):
if dq and dq[0] < i - k + 1: #the element out of range
dq.popleft()
while dq and nums[dq[-1]] <= nums[i]: #the element impossible to be the maximum value in deque
dq.pop()
dq.append(i)
if i > k - 2:
res.append(nums[dq[0]])
return res
