<p>The <strong>median</strong> is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.</p>

<ul>
	<li>For examples, if <code>arr = [2,<u>3</u>,4]</code>, the median is <code>3</code>.</li>
	<li>For examples, if <code>arr = [1,<u>2,3</u>,4]</code>, the median is <code>(2 + 3) / 2 = 2.5</code>.</li>
</ul>

<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. There is a sliding window of size <code>k</code> which is moving from the very left of the array to the very right. You can only see the <code>k</code> numbers in the window. Each time the sliding window moves right by one position.</p>

<p>Return <em>the median array for each window in the original array</em>. Answers within <code>10<sup>-5</sup></code> of the actual value will be accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,-1,-3,5,3,6,7], k = 3
<strong>Output:</strong> [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
<strong>Explanation:</strong> 
Window position                Median
---------------                -----
[<strong>1  3  -1</strong>] -3  5  3  6  7        1
 1 [<strong>3  -1  -3</strong>] 5  3  6  7       -1
 1  3 [<strong>-1  -3  5</strong>] 3  6  7       -1
 1  3  -1 [<strong>-3  5  3</strong>] 6  7        3
 1  3  -1  -3 [<strong>5  3  6</strong>] 7        5
 1  3  -1  -3  5 [<strong>3  6  7</strong>]       6
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,2,3,1,4,2], k = 3
<strong>Output:</strong> [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        min_heap,max_heap = [],[]

        # 初始化
        for i in range(k):
            heapq.heappush(min_heap,(nums[i],i))
        for i in range(k//2):
            n,idx = heapq.heappop(min_heap)
            heapq.heappush(max_heap,(-n,idx))
        
        res = [(min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0]
        
        for i in range(k,len(nums)):
            # 如果新数字应该放到最大堆
            if nums[i] < min_heap[0][0]:
                heapq.heappush(max_heap,(-nums[i],i))
                # 如果要弹出的元素在最小堆中，调整
                if nums[i-k] >= min_heap[0][0]:
                    n,idx = heapq.heappop(max_heap)
                    heapq.heappush(min_heap,(-n,idx))
            else:
                heapq.heappush(min_heap,(nums[i],i))
                # 如果要弹出的元素在最大堆中，调整
                # 取等号是特殊情况
                if nums[i-k] <= min_heap[0][0]:
                    n,idx = heapq.heappop(min_heap)
                    heapq.heappush(max_heap,(-n,idx))
            
            # 将堆顶在窗口外的元素清除出去
            while min_heap and min_heap[0][1] <= i-k:
                heapq.heappop(min_heap)
            while max_heap and max_heap[0][1] <= i-k:
                heapq.heappop(max_heap)
            
            # 添加答案
            res.append((min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0)
            
        return res
  
33378