O(N) LinkedList & O(N(LogK)) Dictionary + SortedSet Solution


  • 0
    L

    O(N) LinkedList

        public int[] MaxSlidingWindow2(int[] nums, int k){
            if (nums.Length == 0 || k == 0) return new int[0];
            int[] result = new int[nums.Length - k + 1];
            LinkedList<int> list = new LinkedList<int>();
            for (int i = 0; i < nums.Length; i++){
                while (list.Count > 0 && nums[i] > list.Last.Value)
                    list.RemoveLast();
                list.AddLast(nums[i]);
                if (i < k - 1) continue;
                result[i - k + 1] = list.First.Value;
                if (nums[i - k + 1] == list.First.Value) list.RemoveFirst();
            }
            return result;
        }
    

    O(N(LogK)) Dictionary + SortedSet

    public int[] MaxSlidingWindow(int[] nums, int k) {
        if (k < 1 || nums.Length == 0) return new int[0];
        int[] result = new int[nums.Length - k + 1];
        Dictionary<int, int> map = new Dictionary<int, int>(nums.Length);
        SortedSet<int> sortSet = new SortedSet<int>();
        for (int i = 0; i < nums.Length; i++){
            sortSet.Add(nums[i]);   // O(LogK)
            map[nums[i]] = i;       // O(1)
            if(i < k - 1) continue;
            if (i >= k && map[nums[i - k]] == i - k)// O(1)
            {
                sortSet.Remove(nums[i - k]);    // O(logK)
                map.Remove(nums[i - k]);        // O(1)
            }
            result[i - k + 1] = sortSet.Max;    // O(1)
        }
        return result;
    }

  • 0

    What about LinkedList?

    The two lines in your main if are the same as the first two lines of your main else, btw. Why not take them out?


  • 0
    L

    Hi Stefan, thanks for catching the redundant part.
    I didn't get what benefit if we use LinkedList to sort the values. Maintain the sorted linked list is expensive I think.


  • 0
    L

    I realized what you are saying. Will try to update it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.