寻找滑窗中的最大值问题

你的名字 2023-01-13 10:18 90阅读 0赞

题目描述  
编程：一个数组，一个长度为k的滑动窗口从左到右滑过这个数组，返回窗口在每一个位置时窗口中最大的值。

例如：3 -1 5 1 3 4 6 2 0，k=3，返回 5 5 5 4 6 6 6

思路：  
直接遍历，逐个寻找滑窗中的最大值。时间复杂度O(kn)，空间复杂度O(n-k+1)

#include<stdio.h>
    void list_max(int *nums1, int nums1Size, int k, int *nums2)
    { 
    
         for(int i =0; i < nums1Size - k + 1; i++)
         { 
              int left = i;
              int right = left + k - 1;
              int max = nums1[i];
              for(int j = left; j <= right; j++)
              { 
                   if(nums1[j] > max)
                   { 
                        max = nums1[j];
                   }
              }
              nums2[i] = max;
         }
    }
    int main()
    { 
         int nums1[9] = { 3, -1, 5, 1, 3, 4, 6, 2, 0};
         int nums1Size = 9;
         int k = 3;
         int returnSize;
         int nums2[nums1Size - k + 1];
    
         list_max(nums1, nums1Size, k, nums2);
         
         for(int i = 0; i < nums1Size - k + 1; i++)
         { 
              printf("%d ", nums2[i]);
         }
    }

改进：  
其实上面我们在滑动的过程中存在一个问题，就是每次滑动之后会有重复比较的情况，比如：比较3 -1 5，然后滑动一次后，比较-1 5 1，这部分会比较两次-1 5，其实我们每次在比较之前首先判断上一次窗口的最大值5是不是窗口第一个值，不是的话直接拿下一个值1和上一次窗口的最大值5比较，如果比其小，那么当前窗口的最大值仍然是5；否则就寻找当前窗口的最大值。

具体实现：首先计算第一个窗口的最大值，后面滑动时，每次先判断上一个窗口的最大值是否是最左端的那个，如果不是，就使窗口的最右端的值与之比较，选择较大的作为当前窗口的最大值，如果是，则需要通过循环比较当前窗口的最大值。

void list_max2(int *nums1, int nums1Size, int k, int *nums2)
    { 
         int maxNum = nums1[0];
         for(int i =0; i < k; i++)
         { 
              if(nums1[i] > maxNum)
              { 
                   maxNum = nums1[i];
              }
         }
         nums2[0] = maxNum;
         int j = 1;
         for(int left = 1; left < nums1Size - k + 1; left++)
         { 
              if(nums1[left-1] == maxNum)
              { 
                   maxNum = nums1[left];
                   for(int i = left; i < left + k; i++)
                   { 
                        if(nums1[i] > maxNum)
                             maxNum = nums1[i];
                   }
                   nums2[j] = maxNum;
                   j++;
              }
              else
              { 
                   if(nums1[left + k - 1] > maxNum)
                   { 
                        maxNum = nums1[left + k -1];
                        nums2[j++] = nums1[left + k - 1];
                   }
                   else nums2[j++] = maxNum;
              }
         }
    }