Leetcode Hot 100 & 239. Sliding Window Maximum

　　参考资料：

　　Python文档heapq部分

　　考点：子串 & [题干]

 1 Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
 2 Output: [3,3,5,5,6,7]
 3 Explanation: 
 4 Window position                Max
 5 ---------------               -----
 6 [1  3  -1] -3  5  3  6  7       3
 7  1 [3  -1  -3] 5  3  6  7       3
 8  1  3 [-1  -3  5] 3  6  7       5
 9  1  3  -1 [-3  5  3] 6  7       5
10  1  3  -1  -3 [5  3  6] 7       6
11  1  3  -1  -3  5 [3  6  7]      7

　　1. 心路历程

　　第一眼看到这个题，想了想，咦~这不就是一维的最大值池化吗，这个有什么好的优化算法吗？首先进入脑子的是一个必定超时的算法，如下：

　　对于窗口的每一次滑动，由于k固定，则可以直接索引窗口内的每一个值，for循环取最大值就一定是正确的结果了。但是这个方法是肯定超时的，因为leetcode官方可以把k设置的比较大。

　　一个优化的思路：

　　受上一题启发，我们实际上可以在一次遍历中得到子串的更多信息。设前缀max值为pre_max，则有  max( pre_max[i], pre_max[i+1:j] ) = pre_max[j] 。这个比较好理解，算出前i个值的最大值为A，i+1~j子串的最大值是B，那么前j个值的最大值一定是两者之间的最大值。进行倒推的话就有如果pre_max[j] == pre_max[i]则，pre_max[i+1:j]的值还是未知数，如果pre_max[j] > pre_max[i]，则子串的值就等于pre_max[j]。这个浅层次的优化对于递增序列有用，但是对于递减序列就完全没有任何作用。所以说这个优化方法不足以让算法不超时。

　　2. 正解

　　后面想不到好的办法就直接看官解了，看完我只想说，leetcode上面的一些题考的并不纯粹，例如排序算法就是纯粹的玩数组。而做leetcode需要你经验丰富并且调用很多builtin的包（也就是用很多内置写好的数据结构）才能完成。例如这道题就使用了优先队列即大根堆这种树形数据结构，以python语言为例，如果你不熟悉（或者说不用）heapq这个内置的优先队列实现包，这道题八成对你有无形的壁垒。说完了数据结构，我再来分析一下官解的思路，其实只是借用大根堆这种数据结构简化了心路历程中对于每一个子串的判断最大值操作。首先把前k个数字装进大根堆，这样最大的数值就在根上了，然后向右移动扫描一位，这样大根堆中就有k+1个数字。然后进行判断，即当前的根节点是否在当前的滑动窗口中，如果不在，出栈，如果在，则根就是当前窗口的最大值。为此使用一个tuple记录(值, index)，再利用大根堆就可以完美实现了，了解了解题思想和工具，下面是自己的实现：

 1 class Solution(object):
 2     def maxSlidingWindow(self, nums, k):
 3         """
 4         :type nums: List[int]
 5         :type k: int
 6         :rtype: List[int]
 7         """
 8         n = len(nums)
 9 
10         myheap = []
11         result = []
12 
13         for i in range(k):
14             heappush(myheap, (-nums[i], i))
15             
16         result.append(-myheap[0][0])
17 
18         for i in range(k, n):
19             heappush(myheap, (-nums[i], i))
20             while myheap[0][1] <= i - k:
21                 heappop(myheap)
22             result.append(-myheap[0][0])
23 
24         return result