K 크기 하위 배열의 성능 찾기 I

3254. K 크기 하위 배열의 힘 찾기 I

난이도:중

주제: 어레이, 슬라이딩 윈도우

길이 n의 정수 nums 배열과 양수 정수 k

가 제공됩니다.

배열의 성능은 다음과 같이 정의됩니다.

• 모든 요소가 연속이고 오름차순으로 정렬된 경우 최대 요소입니다.
• 그렇지 않으면 -1.

모든 하위 배열의 power¹개 크기 k를 찾아야 합니다.

n - k 1 크기의 정수 배열 결과를 반환합니다. 여기서 결과[i]는 nums[i..(i k - 1)]의 제곱입니다.

예 1:

• 입력: nums = [1,2,3,4,3,2,5], k = 3
• 출력: [3,4,-1,-1,-1]
• 설명: 크기가 3인 숫자의 하위 배열이 5개 있습니다.
  • [1, 2, 3] 최대 요소 3.
  • [2, 3, 4] 최대 요소 4.
  • [3, 4, 3]의 요소는 연속되지 않습니다.
  • [4, 3, 2]의 요소는 정렬되지 않습니다.
  • [3, 2, 5]의 요소는 연속되지 않습니다.

예 2:

• 입력: nums = [2,2,2,2,2], k = 4
• 출력: [-1,-1]

예 3:

• 입력: nums = [3,2,3,2,3,2], k = 2
• 출력: [-1,3,-1,3,-1]

제약조건:

• 1
• 1 5
• 1

힌트:

1. 중첩 루프와 HashSet에 무차별 대입 솔루션을 사용할 수 있나요?

해결책:

작업을 다음과 같이 분류할 수 있습니다.

문제 분석:

1. 길이가 n인 배열 num과 양의 정수 k가 주어졌습니다. 크기가 k인 모든 하위 배열을 고려하고 전력을 계산해야 합니다.
2. 하위 배열의 성능은 다음과 같습니다.
   • 모든 요소가 연속이고 오름차순으로 정렬된 경우 하위 배열의 최대
   요소입니다.
   그렇지 않으면 -1.
각 요소가 해당 하위 배열의 거듭제곱에 해당하는 n - k 1 크기의 배열을 반환해야 합니다.

계획:

1. 슬라이딩 윈도우 접근법
: 배열 위로 슬라이드하여 길이 k인 각 하위 배열을 확인합니다.
2. 하위 배열이 정렬되어 있는지 확인
: 하위 배열에 연속적이고 오름차순으로 정렬된 요소가 있는지 확인해야 합니다.
3. 최대값 반환 또는 -1
: 하위 배열이 유효하면 최대값 요소를 반환합니다. 그렇지 않으면 -1을 반환합니다.

단계:

1. 하위 배열이 정렬되어 있는지 확인
   :
   연속 요소가 있는 정렬된 하위 배열은 하위 배열의 모든 i에 대해 nums[i 1] - nums[i] == 1 속성을 가져야 합니다.
2. 슬라이딩 창
   :
   길이가 k인 각 하위 배열에 대해 정렬되었는지 확인하고 유효한 경우 최대 요소를 반환하고, 그렇지 않으면 -1을 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 3254. K 크기 하위 배열의 힘을 찾아보세요 I

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function resultsArray($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(resultsArray([1, 2, 3, 4, 3, 2, 5], 3));  // Output: [3, 4, -1, -1, -1]
print_r(resultsArray([2, 2, 2, 2, 2], 4));  // Output: [-1, -1]
print_r(resultsArray([3, 2, 3, 2, 3, 2], 2));  // Output: [-1, 3, -1, 3, -1]
?>

설명:

• 슬라이딩 윈도우: i = 0부터 i = n - k까지 for 루프를 사용하여 k 크기의 모든 하위 배열을 고려합니다. 각 하위 배열에 대해 array_slice()를 사용하여 하위 배열을 추출합니다.
• 정렬 확인: 각 하위 배열에 대해 하위 배열을 반복하고 각 연속 요소 쌍의 차이가 1인지 확인하여 연속 요소로 정렬되었는지 확인합니다.
• 결과: 하위 배열이 유효하면 하위 배열의 최대값을 결과에 추가합니다. 그렇지 않으면 -1을 추가합니다.

시간 복잡도:

• n - k 1개의 하위 배열을 반복하고 있습니다.
• 각 하위 배열에 대해 요소가 연속적인지 확인하는데 O(k) 시간이 걸립니다.
• 따라서 전체 시간 복잡도는 O((n - k 1) * k)이며 이는 O(n * k)로 단순화됩니다.

극단적인 경우 고려사항:

• k = 1이면 모든 하위 배열은 간단하게 정렬되며(단 하나의 요소만 포함) 각 하위 배열의 성능은 요소 자체가 됩니다.
• 하위 배열이 연속되지 않으면 즉시 -1을 반환합니다.

예제 출력:

1. nums = [1, 2, 3, 4, 3, 2, 5], k = 3인 경우 출력은 [3, 4, -1, -1, -1]입니다.
2. nums = [2, 2, 2, 2, 2], k = 4인 경우 출력은 [-1, -1]입니다.
3. nums = [3, 2, 3, 2, 3, 2], k = 2인 경우 출력은 [-1, 3, -1, 3, -1]입니다.

이 솔루션은 문제 제약 조건에 효율적으로 작동해야 합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

---

1. 하위 배열: 하위 배열은 배열 내 비어 있지 않은 연속된 요소 시퀀스입니다. ↩

위 내용은 K 크기 하위 배열의 성능 찾기 I의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!