Sliding Window Maximum Solution without using Deque


  • 0
    V

    Basic idea is that, I used an pointer maxIndex to record max value's index in a window k, when the window move forward by 1 step, if the previous window's maxIndex is the first element in the previous window, we iterator the new window to find max and maxIndex, if not, we just compare the new added element and the max value.
    Time complexity is O(k*n).

    public class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {
    
        if(nums == null || nums.length == 0){
            return nums;
        }
        
        if(k == 1){
            return nums;
        }
        
        int max = Integer.MIN_VALUE;
        int maxIndex = 0;
        
        int[] ret = new int[nums.length - k + 1];
        int index = 0;
        
        for(int i = 0; i <= nums.length - k; i++){
            if(i == 0 || maxIndex == i - 1){
                max = Integer.MIN_VALUE;
                for(int j = i; j < i + k; j++){
                    if(nums[j] > max){
                        max = nums[j];
                        maxIndex = j;
                    }
                }
            }else{
                if(nums[i + k - 1] > max){
                    max = nums[i + k - 1];
                    maxIndex = i;
                }
            }
            ret[index] = max;
            index++;
        }
        
        return ret;
    }
    

    }


Log in to reply
 

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