leetcode sliding window maximum (Java)

Leetcode summary: Classic programming topic of leetcode (Java implementation)

leetcode topic

Maximum sliding window -- leetcode 239

Title Description

Given an array of nums, there is a sliding window of size k that moves from the leftmost to the rightmost of the array. You can only see the numbers in the sliding window K. The sliding window moves only one bit to the right at a time.

Returns the maximum sliding window value.

Example:

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

  Maximum position of sliding window
---------------               -----
[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
 Be careful:

You can assume that k is always valid, 1 ≤ k ≤ the size of the input array, and the input array is not empty.

Advance:

Can you solve this problem in linear time complexity?

Source: LeetCode
 Link: https://leetcode-cn.com/problems/sliding-window-maximum

thinking

 *1. Double end queue, the maximum value is placed in the queue head
 *2. If a value is larger than the value in front of it, the value in front of it will never be the maximum value.
 *2. Because the current element is larger than the previous one, the maximum value of the current window is the current element, otherwise it is the maximum value of the window.

Code

package com.my.test.leetcode.array;

import java.util.LinkedList;

/**
 * Title:
 * Maximum sliding window -- leetcode 239
 * 
 * Title Description:
 * 
Given an array of nums, there is a sliding window of size k that moves from the leftmost to the rightmost of the array. You can only see the numbers in the sliding window K. The sliding window moves only one bit to the right at a time.

Returns the maximum sliding window value.

Example:

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

  Maximum position of sliding window
---------------               -----
[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
 Be careful:

You can assume that k is always valid, 1 ≤ k ≤ the size of the input array, and the input array is not empty.

Advance:

Can you solve this problem in linear time complexity?

Source: LeetCode
 Link: https://leetcode-cn.com/problems/sliding-window-maximum
 Copyright belongs to the network. For commercial reprint, please contact the official authorization. For non-commercial reprint, please indicate the source.
 */
public class MaxSlidingWindow
{
    /**
     * Train of thought:
     * 1,Double ended queue, the maximum value is placed in the queue head
     * 2,If a value is larger than the value in front of it, the value in front of it can never be the maximum value
     * 2,Because the current element is larger than the previous one, the maximum value of the current window is the current element, otherwise it is the maximum value of the window.
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length <= 0 || k <= 0) {
            return new int[0];
        }
        int len = nums.length;
        // k is valid without checking k
        int[] res = new int[len - k + 1];
        
        // Double ended queue
        LinkedList<Integer> cache = new LinkedList<>();
        
        for (int i=0; i<len; i++) {
            // Add elements to the queue, ensure that the queue is increasing, and pop up the smaller ones
            while (!cache.isEmpty() && nums[cache.peekLast()] < nums[i]) {
                // Add element index to the queue
                cache.removeLast();
            }
            // Add element index to the queue
            cache.addLast(i);
            // Expired elements in the queue need to be removed
            if (i - cache.peekFirst() >= k) {
                cache.removeFirst();
            }
            // If I > = k-1 in the queue, record the maximum value in the current queue
            if (i >= k - 1) {
                res[i-k+1] = nums[cache.peekFirst()];
            }
        }
        
        return res;
    }
    
    public static void main(String[] args)
    {
        int[] nums = {1,3,1,2,0,5}; 
        int k = 3;
        System.out.println(new MaxSlidingWindow().maxSlidingWindow(nums, k));
        int[] nums1 = {1,-1}; 
        int k1 = 1;
        System.out.println(new MaxSlidingWindow().maxSlidingWindow(nums1, k1));
    }

}

Tags: Java Programming network

Posted on Sun, 03 Nov 2019 00:28:59 -0700 by iHack