239. Sliding Window Maximum

You are given an array of integers nums ,there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example : Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max

---

[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

Approach :

1. N is a number of elements in an array and k is the window size. Then, Window number is N- K+1
2. Now divide the array into block of k starting from 1. \ Sample : [ 1,3,-1 | -3,5,3 | 6,7 ]
3. We will use two another array left and right to get maximum of each block. In 'left' we traverse
   left to right and in 'right' we traverse right to left.
4. In left , we traverse from left to right, we find maximum element from start of the block to the
   end of that block nums = 1, 3, -1 | -3, 5, 3 | 6, 7 left = 1, 3, 3 | -3, 5, 5 | 6, 7
5. In right , we traverse from right to left, we find maximum element from end of the block to
   start to that block. nums = 1, 3 -1 | -3 ,5, 3 | 6,7 right = 3, 3, -1, | 5, 5, 3, | 7, 7

6. Now we have to find maximum for each subarray or window of size K. So, starting from index
   = 1 to index = N-K+1 .

   NUMS : 1, 3, -1, | -3, 5, 3, | 6, 7 LFT : 1, 3, 3, | -3, 5, 5, | 6, 7 RGT : 3, 3, -1, | 5, 5, 3, | 7, 7

   result[index] = max(right[index], left[index+k-1]);

   So Final Answer : 3, 3, 5, 5, 6, 7

   Time Complexity: O(n)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int left[] = new int[len];
        int right[] = new int[len];
        int now = len-k+1;
        int result[] = new int[now];
        right[len-1] = nums[len-1];
        for(int i=0;i<len;i++){
            left[i] = nums[i];
            if(i%k!=0){

                if(left[i-1]>left[i]){
                    left[i] = left[i-1];
                }else{
                    left[i] = left[i];
                }
            }
        }
        for(int i=len-2;i>=0;i--){
            right[i] = nums[i];
            if(i%k!=(k-1)){
                if(right[i+1]>right[i]){
                    right[i] = right[i+1];
                }else{
                    right[i] = right[i];
                }
            }
        }
        for(int i=0;i<now;i++){
            if(left[i+k-1]>right[i]){
                result[i] = left[i+k-1];
            }else{
                result[i] = right[i];
            }
        }
        return result;
    }
}