Leetcode 239 - sliding window maximum - pass online judge

Leetcode239_slidingWindowMaximum.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace slidingWindowMaximum
{
    class slidingWindowMaximum1
    {
        static void Main(string[] args)
        {
            RunTestcase(); 
        }

        public static void RunTestcase()
        {
            var testcase = new int[] {1, 3, -1, -3, 5, 3, 6, 7 };
            var maximums = MaxSlidingWindow(testcase, 3);
            Debug.Assert(maximums[0] == 3); 
        }

        /*
         * 
         * [LeetCode Plus] Sliding Window Maximum
         * A long array A[] is given to you. There is a sliding window of size w which 
         * is moving from the very left of the array to the very right. You can only 
         * see the w numbers in the window. Each time the sliding window moves rightwards 
         * by one position. Following is an example: The array is [1, 3, -1, -3, 5, 3, 6, 7], 
         * and w is 3.
         * Window position                Max           Queue         Queue Mapped numbers
            ---------------               -----         ------        ----------------------
            [1  3  -1] -3  5  3  6  7       3           [1,2]         [1->3, 2->-1]
             1 [3  -1  -3] 5  3  6  7       3           [1,2,3]       [1->3, 2->-1, 3->-3]
             1  3 [-1  -3  5] 3  6  7       5           [4]           [4->5]
             1  3  -1 [-3  5  3] 6  7       5           [4, 5]        [4->5, 5->3]
             1  3  -1  -3 [5  3  6] 7       6           [6]           [6->6]
             1  3  -1  -3  5 [3  6  7]      7           [7]           [7->7]
         * 
         *  Input: A long array A[], and a window width w
            Output: An array B[], B[i] is the maximum value of from 
         *  A[i] to A[i + w - 1]
         *  
         *
         *
         * source code from blog:
         * http://www.shuatiblog.com/blog/2014/07/27/Sliding-Window-Maximum/
         * comment from blog:
         * The naive approach is using a Heap. This time complexity is O(n*logn). 
         * However, there is a better way using a (double-ended) queue.
            We do not need to keep all numbers. For example, suppose numbers in 
         *  a window of size 4 are (1, 3, -1, 2). Obviously, no matter what next 
         *  numbers are, 1 and -1 are never going to be a maximal as the window 
         *  moving. The queue should look like (3, 2) in this case.
         *  
         *  Solution
            When moves to a new number, iterate through back of the queue, removes 
         *  all numbers that are not greater than the new one, and then insert 
         *  the new one to the back.
            FindMax only need to take the first one of the queue.
            To remove a number outside the window, only compare whether the current 
         *  index is greater than the front of queue. If so, remove it.
            A natural way most people would think is to try to maintain the queue size 
         *  the same as the window’s size. Try to break away from this thought and 
         *  think out of the box.                               
         *            
         *  
         *  Julia's comment on August 8, 2015:
         *  
         *  1. The pruning on the queue is a smart idea, otherwise there are n-w windows, 
         *     to calculate the maximum n-w times, time complexity will be O(w*(n-w)) = O(wn); 
         *  2. How to save the calculation time complexity from reducing O(nw) to O(n)? 
         *  3. Let me try to convert the code to C# first. 
         *  4. Get some experience with C# LinkedList class first. 
         *  5. Leetcode online judge: 
         *  failed the test case:
         *  [], 0
         *  output [0]
         *  expect []
         *  6.  Several facts to understand the code:
         *    1. about the queue:
         *    it is non-increasing order, the maximum value's index is the first one in the queue. 
         *    
         * Julia reviewed the code on June 8, 2017. 
         * 1. Change the variable names
         * 2. Queue is implemented using LinkedList, put the index of number in the queue. 
         * 3. Add the test case in the code, and also do whiteboard testing. 
         * 4. LinkedList API  members 
         *    LinkedList.Last, 
         *    LinkedList.First
         *    LinkedList.RemoveFirst
         *    LinkedList.RemoveLast
         */
        public static int[] MaxSlidingWindow(int[] nums, int k)
        {
            if (k == 0)
            {
                return nums; // julia: base case is added to pass online judge. 
            }

            int length = nums.Length;
            int numberOfSlidingWindow = length - k + 1;

            var maximums = new int[numberOfSlidingWindow];

            var linkedList = new LinkedList<int>();  // LinkedList acts like deque

            for (int index = 0; index < length; index++)
            {
                var current = nums[index]; 

                // Remove the first number in the queue if it falls out of the sliding window
                if (linkedList.Count > 0 && linkedList.First.Value + k <= index)
                {
                    linkedList.RemoveFirst();
                }

                // Visit the current number, remove from the tail of the
                // queue indices if the value is smaller than the current number.
                while (linkedList.Count > 0 && nums[linkedList.Last.Value] <= current)
                {
                    linkedList.RemoveLast();
                }

                linkedList.AddLast(index);

                // Set the max value in the window (always the top number in the queue)                
                int maximumsIndex = index + 1 - k;
                if (maximumsIndex >= 0)
                {
                    maximums[maximumsIndex] = nums[linkedList.First.Value];
                }
            }

            return maximums;
        }
    }
}