<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 = [], []  # min_heap存储较大的一半，max_heap存储较小的一半
        res = []
        
        # 初始化，处理前k个元素
        for i in range(k):  # 先将前k个元素放入最小堆中
            heappush(min_heap, (nums[i], i))
        
        # 将最小堆的一半元素移到最大堆中
        for i in range(k // 2):
            tmp, idx = heappop(min_heap)
            heappush(max_heap, (-tmp, idx))  # 注意最大堆存的是负数，用于模拟最大堆
        
        # 计算第一个窗口的中位数
        res.append((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]:
                heappush(max_heap, (-nums[i], i))
                # 如果要弹出的元素在最小堆中，调整平衡
                if nums[i - k] >= min_heap[0][0]:
                    n, idx = heappop(max_heap)
                    heappush(min_heap, (-n, idx))
            else:
                heappush(min_heap, (nums[i], i))
                # 如果要弹出的元素在最大堆中，调整平衡
                if nums[i - k] <= min_heap[0][0]:
                    n, idx = heappop(min_heap)
                    heappush(max_heap, (-n, idx))

            # 清理掉堆中已经不在窗口内的元素
            while min_heap and min_heap[0][1] <= i - k:
                heappop(min_heap)
            while max_heap and max_heap[0][1] <= i - k:
                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

"""
class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        min_heap = []
        max_heap = []
        res = []
        for i in range(k):
            heappush(max_heap,(nums[i],i))#have a bigger size 
        for i in range(len(k)//2):
            tmp,idx = heappop(max_heap)
            heappush(min_heap,(-tmp,idx))
        res=[max_heap[0][0]] if k%2 == 1 else res = (max_heap[0][0]-min_heap[0][0])//2
        for i in range(k,len(nums)-k+1):
            if nums[i]> -min_heap[0][0]:
                heappush(min_heap,(-nums[i],i))
                if len(min_heap) > len(max_heap) + 1:
                    heappush(max_heap,(-heappop(min_heap)[0],heappop(min_heap)[1]))
            if nums[i] < max_heap[0][0]:
                heappush(max_heap,(nums[i],i))
                if len(min_heap)  <len(max_heap) :
                    heappush(min_heap,(-heappop(max_heap)[0],heappop(max_heap)[1]))

            #问题：如果有过期元素不在堆顶怎么办？
假设有一个过期的元素 6（索引 7），它在 min_heap 中但不在堆顶。此时，我们不会立即移除它，直到它成为堆顶时才会处理。这种做法不会影响中位数的正确性，因为我们只关心堆顶的有效性。

为什么这不会导致错误？
即使有过期元素不在堆顶，它们也不会参与中位数的计算。我们只从堆顶取出中位数，因此只要堆顶元素是有效的（即没有过期），计算的结果就是正确的。

过期元素虽然还在堆中，但只要它不在堆顶，我们不会误用它。等到它变成堆顶时，它会被正确地删除。

"""
34528