Python Solution with deque


  • 3
    B
     class Solution(object):
            def maxSlidingWindow(self, nums, k):
                """
                :type nums: List[int]
                :type k: int
                :rtype: List[int]
                """
                queue = [] # like PriorityQueue, remain the top k value
                result = []
        
                for i in xrange(len(nums)):
                    # judge whether the first item is in window
                    if queue and queue[0] < i - k + 1:
                        queue.pop(0)
        
                    # update the queue 
                    while queue and nums[queue[-1]] < nums[i]:
                        queue.pop()
        
                    queue.append(i)
                    
                    #after i > k - 1, output the max value
                    if queue and i >= k - 1:
                        result.append(nums[queue[0]])
            return result

  • 0
    M

    public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0) return new int[0];
    for (int i = 1 ; i < k; i++) {
    int l = nums.length - i;
    for (int j = 0; j < l; j++) {
    nums[j] = Math.max(nums[j], nums[j + 1]);
    }
    }
    return Arrays.copyOf(nums, nums.length - k + 1);
    }
    }


Log in to reply
 

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