Leetcode question brushing: stack and queue 07 (maximum value of sliding window)

239. Maximum sliding window

Force button topic link

Given an array nums, There is a size of k The sliding window of the array moves from the leftmost side to the rightmost side of the array . You can only see... In the sliding window k A digital . The sliding window moves only one bit to the right at a time .

Returns the maximum value in the sliding window .

Advanced ：

Can you solve this problem in linear time complexity ？

Tips ：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

All the way through the stumbling .
I got this question originally , It seems not difficult , It's still difficult ？？？

Write the code in a few lines

    public int[] maxSlidingWindow(int[] nums, int k) {
    
        /** *  Input ：nums = [1,3,-1,-3,5,3,6,7], k = 3 *  Output ：[3,3,5,5,6,7] *  common  8  Number , Slide in groups of three , It can be made up of  8-3+1  Group , namely  6  Group  */
        if (nums.length < 2) {
    
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length - k + 1; i++) {
    
            int max = -10000;
            for (int j = i; j < i + k; j++) {
    
                if (nums[j] > max) {
    
                    max = nums[j];
                }
            }
            result[i] = max;
        }
        return result;
    }

I can only say ： What a long test case ...
Then improve your thinking , Change violent cracking to sliding . Divide a window into the following parts .

left Is the current maximum expiration
right Is the new value
mid Is the last maximum , Is the maximum of that old interval , As shown in the figure ： At present mid=3
Every time the window moves back , Let's see if the previous maximum can still be used （ Whether the maximum value is equal to left The value of is the same , The same cannot be used , You have to traverse the window again to find the maximum value ）; If you can use it, continue to use it .

   public int[] maxSlidingWindow(int[] nums, int k) {
    
        if (nums.length < 2) {
    
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        /** *  If the maximum value of the current range element is still the maximum value of the next range , Continue to use . *  Here we need to judge whether the current position has passed  */
        int maxValue = -10000;
        for (int j = 0; j < k; j++) {
    
            if (nums[j] > maxValue) {
    
                maxValue = nums[j];
            }
        }
        result[0] = maxValue;
        // front k The two have been compared 
        int resIndex = 1;
        // Abstract it out , Left boundary value , The maximum value of the middle part , Right boundary value 
        for (int i = k; i < nums.length; i++) {
    
            // Just expired left boundary 
            int left = nums[i - k];
            int mid = maxValue;
            int right = nums[i];

            if (left>mid-1) {
    
                // If expired , You have to find the maximum again 
                    maxValue = -10000;
                for (int j = i - k + 1; j < i + 1; j++) {
    
                    if (nums[j] > maxValue) {
    
                        maxValue = nums[j];
                    }
                }
            }

            // If the new element is larger than the original 
            if (right >= mid) {
    
                maxValue = right;
            }
            result[resIndex] = maxValue;
            resIndex++;
        }
        return result;
    }

emmmm There's progress , This pass 49 individual , There are only two left . After pondering hard , Finally let me see something different .

So many kinds . In order to improve efficiency , In addition to proving that the maximum value is and left The value of is the same , The update proves that the maximum value is just eliminated left The maximum of . So I changed a line of code . Passed .

   public static int[] maxSlidingWindow2(int[] nums, int k) {
    
        /** *  Input ：nums = [1,3,-1,-3,5,3,6,7], k = 3 *  Output ：[3,3,5,5,6,7] *  common  8  Number , Slide in groups of three , It can be made up of  8-3+1  Group , namely  6  Group  */
        if (nums.length < 2) {
    
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        /** *  If the maximum value of the current range element is still the maximum value of the next range , Continue to use . *  Here we need to judge whether the current position has passed  */
        int maxValue = -10000;
        for (int j = 0; j < k; j++) {
    
            if (nums[j] > maxValue) {
    
                maxValue = nums[j];
            }
        }
        result[0] = maxValue;
        // front k The two have been compared 
        int resIndex = 1;
        // Abstract it out , Left boundary value , The maximum value of the middle part , Right boundary value 
        for (int i = k; i < nums.length; i++) {
    
            // Just expired left boundary 
            int left = nums[i - k];
            int mid = maxValue;
            int right = nums[i];
            // Partial optimization , Prevent consecutive repeated numbers 
            // If left That's the maximum 
            if (left > mid - 1 && left != nums[i - k + 1]) {
    
                // If expired , You have to find the maximum again 
                maxValue = -10000;
                for (int j = i - k + 1; j < i + 1; j++) {
    
                    if (nums[j] > maxValue) {
    
                        maxValue = nums[j];
                    }
                }
            }

            // If the new element is larger than the original 
            if (right >= mid) {
    
                maxValue = right;
            }
            result[resIndex] = maxValue;
            resIndex++;
        }
        return result;
    }

perfect AC !