<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 {
    public:
        vector<double> medianSlidingWindow(vector<int>& nums, int k) {
                vector<double> medians;
                        unordered_map<int, int> outgoingNum;
                                priority_queue<int> smallList;
                                        priority_queue<int, vector<int>, greater<int>> largeList;

                                                for (int i = 0; i < k; i++) {
                                                            smallList.push(nums[i]);
                                                                    }

                                                                            for (int i = 0; k && i < k / 2; i++) {
                                                                                        largeList.push(smallList.top());
                                                                                                    smallList.pop();
                                                                                                            }

                                                                                                                    int balance = 0;
                                                                                                                            int i = k;

                                                                                                                                    while (true) {
                                                                                                                                                if (k % 2 == 1) {
                                                                                                                                                                medians.push_back(smallList.top());
                                                                                                                                                                            } else {
                                                                                                                                                                                            medians.push_back(
                                                                                                                                                                                                                ((long long)smallList.top() + (long long)largeList.top()) *
                                                                                                                                                                                                                                    0.5);
                                                                                                                                                                                                                                                }

                                                                                                                                                                                                                                                            if (i >= nums.size()) {
                                                                                                                                                                                                                                                                            break;
                                                                                                                                                                                                                                                                                        }

                                                                                                                                                                                                                                                                                                    int outNum = nums[i - k];
                                                                                                                                                                                                                                                                                                                int inNum = nums[i];
                                                                                                                                                                                                                                                                                                                            i++;

                                                                                                                                                                                                                                                                                                                                        if (outNum <= smallList.top()) {
                                                                                                                                                                                                                                                                                                                                                        balance -= 1;
                                                                                                                                                                                                                                                                                                                                                                    } else {
                                                                                                                                                                                                                                                                                                                                                                                    balance += 1;
                                                                                                                                                                                                                                                                                                                                                                                                }

                                                                                                                                                                                                                                                                                                                                                                                                            outgoingNum[outNum]++;

                                                                                                                                                                                                                                                                                                                                                                                                                        if (!smallList.empty() && inNum <= smallList.top()) {
                                                                                                                                                                                                                                                                                                                                                                                                                                        balance += 1;
                                                                                                                                                                                                                                                                                                                                                                                                                                                        smallList.push(inNum);
                                                                                                                                                                                                                                                                                                                                                                                                                                                                    } else {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    balance -= 1;
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    largeList.push(inNum);
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            if (balance < 0) {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            smallList.push(largeList.top());
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            largeList.pop();
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        } else if (balance > 0) {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        largeList.push(smallList.top());
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        smallList.pop();
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                balance = 0;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            while (!smallList.empty() && outgoingNum[smallList.top()]) {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            outgoingNum[smallList.top()]--;
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            smallList.pop();
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    while (!largeList.empty() && outgoingNum[largeList.top()]) {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    outgoingNum[largeList.top()]--;
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    largeList.pop();
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                return medians;
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    };

39770