<p>You are given an array of integers&nbsp;<code>nums</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 max sliding window</em>.</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> [3,3,5,5,6,7]
<strong>Explanation:</strong> 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       <strong>3</strong>
 1 [3  -1  -3] 5  3  6  7       <strong>3</strong>
 1  3 [-1  -3  5] 3  6  7      <strong> 5</strong>
 1  3  -1 [-3  5  3] 6  7       <strong>5</strong>
 1  3  -1  -3 [5  3  6] 7       <strong>6</strong>
 1  3  -1  -3  5 [3  6  7]      <strong>7</strong>
</pre>

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

<pre>
<strong>Input:</strong> nums = [1], k = 1
<strong>Output:</strong> [1]
</pre>

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

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

struct Pair
{
    int value;
    int index;
};

class Heap
{
    vector<Pair> heap;
    unordered_map<int, int> indexes;

public:
    void swapHeapNode(int pos1, int pos2)
    {
        if (pos1 == pos2)
        {
            return;
        }

        Pair p = Pair({heap[pos1].value, heap[pos1].index});
        heap[pos1] = heap[pos2];
        heap[pos2] = p;

        // Update the map
        this->indexes[heap[pos1].index] = pos1;
        this->indexes[heap[pos2].index] = pos2;
    }

    void bubbleUp(int pos)
    {
        while (pos > 0)
        {
            int parent = (pos - 1) / 2;
            if (heap[parent].value >= heap[pos].value)
            {
                break;
            }

            this->swapHeapNode(pos, parent);
            pos = parent;
        }
    }

    void bubbleDown(int pos)
    {
        // Buble down the position.
        while (true)
        {
            int left = pos * 2 + 1;
            int right = pos * 2 + 2;
            if (left >= heap.size())
            {
                break;
            }

            if (heap[left].value > heap[pos].value && ((right < heap.size() && heap[left].value >= heap[right].value) || right >= heap.size()))
            {
                this->swapHeapNode(left, pos);
                pos = left;
            }
            else if (right < heap.size() && heap[right].value > heap[pos].value)
            {
                this->swapHeapNode(right, pos);
                pos = right;
            }
            else
            {
                break;
            }
        }
    }

    void insert(int value, int index)
    {
        heap.push_back(Pair{value, index});
        this->indexes[index] = heap.size() - 1;

        int pos = heap.size() - 1;
        this->bubbleUp(pos);
    }

    int getMax()
    {
        return this->heap[0].value;
    }

    void removeIndex(int index)
    {
        if (!this->indexes.count(index))
        {
            throw std::invalid_argument("Cannot find index");
        }

        // position in the heap
        int pos = this->indexes[index];

        // if (index == 75)
        // {
        //     cout << "AAAAA " << pos << " " << heap[pos].value << endl;
        //     this->print();
        // }

        // swap this position with the last element.
        this->swapHeapNode(pos, this->heap.size() - 1);

        // Remove the last element.
        this->indexes.erase(heap[heap.size() - 1].index);
        heap.pop_back();
        if (heap.size() == 0)
        {
            return;
        }

        // if (index == 75)
        // {
        //     cout << "AAAAA " << pos << " " << heap[pos].value << endl;
        //     this->print();
        // }

        int parent = (pos - 1) / 2;
        if (pos > 0 && heap[parent].value < heap[pos].value)
        {
            // bubble up.
            this->bubbleUp(pos);
        }
        else
        {
            this->bubbleDown(pos);
        }
    }

    void print()
    {
        for (auto x : this->heap)
        {
            cout << x.value << " ";
        }
        cout << endl
             << endl;
    }
};

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        Heap heap;
        for (int i = 0; i < k; i++)
        {
            heap.insert(nums[i], i);
        }

        vector<int> result;
        result.push_back(heap.getMax());

        for (int i = k; i < nums.size(); i++)
        {
            // int t = 81;
            // if (nums[i - k] == 7954)
            // {
            //     cout << "BBBBB " << i << endl;
            // }
            // if (i == t)
            // {
            //     heap.print();
            // }
            heap.removeIndex(i - k);
            // if (i == t)
            // {
            //     heap.print();
            // }

            heap.insert(nums[i], i);
            result.push_back(heap.getMax());

            // if (i == t)
            // {
            //     heap.print();
            // }
        }

        return result;
    }
};
195381