leetcode 검 은 offer 면접 문제 59 - I. 슬라이딩 창의 최대 치 를 가리킨다

문제:
배열 nums 와 미끄럼 창의 크기 k 를 지정 합 니 다. 모든 미끄럼 창의 최대 값 을 찾 으 십시오.

  : nums = [1,3,-1,-3,5,3,6,7],   k = 3
  : [3,3,5,5,6,7] 
  : 

                            
---------------               -----
[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

문제 풀이 방향: 단조 로 운 대기 열 에서 창 구간 을 [i, j] 로 설정 하고 최대 값 은 Xj 입 니 다. 창 이 한 칸 이동 하면 구간 은 [i + 1, j + 1] 로 바 뀌 고 nums [j + 1] 를 추가 하여 nums [i] 를 삭 제 했 습 니 다. 오른쪽 경계 에 nums [j + 1] 만 추가 하면 최대 값 은 원래 창 이 새로 추 가 된 숫자 만큼 커 집 니 다. 한 번 의 대비 O (1) 를 통 해 이 루어 집 니 다.그러나 삭 제 된 nums [i] 는 창의 최대 값 일 수 있 기 때문에 O (j - i) 를 사용 해 야 합 니 다. 창 을 옮 겨 다 니 며 최대 값 을 얻 을 수 있 습 니 다.
코드 구현:

int fun(int* nums, int i, int j){
            //  [i, j]      
    int max = nums[i];
    for (int k = i; k <= j; k++){
     
        if (nums[k] > max){
     
            max = nums[k];
        }
    }
    return max;
}

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
     
    if (numsSize == 0){
     
        * returnSize = 0;
        return 0;
    }
    int left;
    int right;
    int p = 0;
    int max = fun(nums, 0, k - 1);
    int* res = (int*)malloc(sizeof(int) * numsSize);
    res[p++] = max;                                 //           
    for (right = k; right < numsSize; right++){
          //    
        left = right - k + 1;
        if (nums[left - 1] != max){
                      //        ，          
            if (nums[right] > max){
                      //             
                max = nums[right];
            }
        }
        else {
     
            max = fun(nums, left, right);          //          ，          
        }
        res[p++] = max;
    }
    * returnSize = p;
    return res;
}