Sliding Window Maximum - 500th problem solved

There is literally no practical benefit for me in solving algo problems. None. Just a hobby that I've been enjoying since I wrote my first algorithm to do a "summation of few numbers". Felt like magic. Still does.

This is my 500th LeetCode problem solved: https://leetcode.com/problems/sliding-window-maximum/solution/

239. Sliding Window Maximum

Hard

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Best algorithm I could come up with uses a SortedList data structure in C#. It allows you to index the elements using the key, as well as retrieve the max element. Although theoretically the SortedList will take O(k), in reality due to its better memory utilization it will perform better than the SortedDictionary which is theoretically an O(logk) data structure. I actually tried both and the former passed (albeit barely) whereas the latter timed out. For more info about these data structures, check https://medium.com/@lifei.8886196/sorted-data-structure-in-c-an-introduction-to-sorteddictionary-sortedlist-and-sortedset-19a69fe184e0.
Add/remove as you land on a new window of size k, take the max and add to the result array. Does the trick. Cheers, ACC.

public class Solution
{
    public int[] MaxSlidingWindow(int[] nums, int k)
    {
        if (nums.Length == 0) return nums;

        SortedList<int, int> window = new SortedList<int, int>();
        int[] retVal = new int[nums.Length - k + 1];
        int index = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            if (i < k)
            {
                if (window.ContainsKey(nums[i])) window[nums[i]] = window[nums[i]] + 1;
                else window.Add(nums[i], 1);
            }
            else
            {
                retVal[index++] = window.Last().Key;

                //Remove i-k
                if (window.ContainsKey(nums[i - k]))
                {
                    window[nums[i - k]] = window[nums[i - k]] - 1;
                    if (window[nums[i - k]] == 0)
                    {
                        window.Remove(nums[i - k]);
                    }
                }

                //Add i
                if (window.ContainsKey(nums[i])) window[nums[i]] = window[nums[i]] + 1;
                else window.Add(nums[i], 1);
            }
        }
        retVal[index++] = window.Last().Key;

        return retVal;
    }
}