describe

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

Returns the maximum value in the sliding window.

Example:

Input: nums = [1, 3, 1, 3,5,3,6,7], and k = 3 output:,3,5,5,6,7 [3] : The position of the sliding window Maximum -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- [1] 3-1-3 3 5 6 7 3 1 [3-1-3] 3 5 6 7 3 1 3 [1-3-5] 3 6 7 5 3-1/3-3 5 6 7 5 1 3 1-3 [5 3 6] 7 6 1 3 1-3 5 [3 6 7] 7Copy the code

Idea 1

  1. Find the largest element Max in the first k numbers
  2. Moves the array fromk+1Start traversing ifnums[k+1] > maxMax = nums[k+1]
[3  -1  -3] 5
5 > 3
max = 5
Copy the code
  1. ifnums[k+1] <= max, need to judge the currentmaxIs it located at the beginning of the window,
  2. ifmaxIf it is located at the beginning of the window, it will be removedmax, re-determine the maximum value in the current window
[3, 2, 1] 2 3 > 2, but 3 is at the beginning of the window, which needs to be removed and the maximum value is determined to be 2Copy the code
  1. ifmaxNot at the beginning of the window, indicates the currentmaxIt’s still the maximum value in the new window.

code

Int maxValue(int *array, int start, int end) {int Max = array[start]; for(int i = start+1; i <= end; i++) { max = array[i] > max ? array[i] : max; } return max; } int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) { *returnSize = numsSize-k+1; int *res = (int*)malloc(sizeof(int)*(*returnSize)); Int Max = maxValue(nums, 0, k-1); int Max = maxValue(nums, 0, k-1); for(int i = 0; i < *returnSize-1; I ++) {// assign res[I] = Max; If (Max > nums[I +k]) {if(Max == nums[I]) {Max = maxValue(nums, I +1, I +k); } }else { max = nums[i+k]; } // if the value of the last window is the maximum value, we need to perform the assignment again. return res; }Copy the code

Idea 2

Maintain a decrement array, which stores the decrement elements in the current window. Compare the largest element with the next element in the current window each time. The judgment process is similar to idea 1, but the way of calculating the maximum value of the window is different.

int* maxSlidingWindow1(int* nums, int numsSize, int k, int* returnSize){ int *queue = (int*)malloc(sizeof(int)*numsSize); *returnSize = numsSize - k + 1; int *res = (int*)malloc(sizeof(int)*(*returnSize)); int resIndex = 1; int front = 0; int rear = -1; for(int i = 0; i < numsSize; While (rear >= front &&nums [I] > queue[rear]) {rear--; } queue[++rear] = nums[i]; If (I <k) {// if(I <k) {res[0] = queue[front]; If (queue[front] == nums[i-k]) {front++; if(queue[front] == nums[i-k]) {front++; } // the maximum value of the new window is the first element of the new array res[resIndex++] = queue[front]; } } return res; }Copy the code