작업 적용 후 배열의 최대 아름다움

2779. 연산 적용 후 배열의 최대 아름다움

난이도:중

주제: 배열, 이진 검색, 슬라이딩 윈도우, 정렬

인덱스가 0인 배열 nums와 음수가 아닌 정수 k가 제공됩니다.

한 번의 작업으로 다음을 수행할 수 있습니다.

• [0, nums.length - 1] 범위에서 이전에 선택되지 않은 인덱스 i를 선택합니다.
• nums[i]를 [nums[i] - k, nums[i] k] 범위의 정수로 바꿉니다.

배열의 아름다움은 동일한 요소로 구성된 가장 긴 부분 수열의 길이입니다.

연산을 여러 번 적용한 후 배열 숫자의 최대값을 반환합니다.

참고 각 인덱스에는 한 번만 작업을 적용할 수 있습니다.

배열의 하위 시퀀스는 나머지 요소의 순서를 변경하지 않고 일부 요소(없을 수도 있음)를 삭제하여 원래 배열에서 생성된 새 배열입니다.

예 1:

• 입력: nums = [4,6,1,2], k = 2
• 출력: 3
• 설명: 이 예에서는 다음 작업을 적용합니다.
  • 인덱스 1을 선택하고 4(범위 [4,8]), nums = [4,4,1,2]로 바꿉니다.
  • 인덱스 3을 선택하고 4(범위 [0,4]), nums = [4,4,1,4]로 바꿉니다.
  • 적용된 연산 후 배열 nums의 아름다움은 3입니다(인덱스 0, 1, 3으로 구성된 하위 시퀀스).
  • 3이 우리가 달성할 수 있는 최대 길이임을 입증할 수 있습니다.

예 2:

• 입력: nums = [1,1,1,1], k = 10
• 출력: 4
• 설명: 이 예에서는 어떤 작업도 적용할 필요가 없습니다.
  • 배열 숫자의 아름다움은 4(전체 배열)입니다.

제약조건:

• 1 5
• 0 5

힌트:

1. 배열을 정렬하세요.
2. 문제는 다음과 같습니다. A[j] - A[i] ≤ 2 * k가 되는 최대 하위 배열 A[i … j]를 찾습니다.

해결책:

정렬과 슬라이딩 윈도우 방식을 활용할 수 있습니다.

접근하다:

1. 배열 정렬: 정렬은 가장 큰 요소와 가장 작은 요소의 차이가 2k.
를 초과하지 않는 하위 시퀀스 식별을 단순화합니다.
2. 슬라이딩 윈도우 기술: 인덱스 창 유지 [i, j] 차이 nums[j] - nums[i] . i 또는 j를 조정하여 창 크기를 최대화하세요.

PHP에서 이 솔루션을 구현해 보겠습니다: 2779. 연산 적용 후 배열의 최대 아름다움

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

// Example Usage:
$nums1 = [4, 6, 1, 2];
$k1 = 2;
echo maximumBeauty($nums1, $k1) . "\n"; // Output: 3

$nums2 = [1, 1, 1, 1];
$k2 = 10;
echo maximumBeauty($nums2, $k2) . "\n"; // Output: 4
?>

설명:

1. 배열 정렬:
   • 정렬을 사용하면 인덱스 [i, j]로 정의된 창에 모든 요소가 오름차순으로 포함되므로, 창문.
2. 슬라이딩 창:
   • 처음에는 i와 j를 모두 시작하세요.
   • j를 증가시켜 창을 확장하고 nums[j] - nums[i] > 조건이 충족될 때마다 i를 증가시켜 창을 유효하게 유지합니다. 2k 위반입니다.
   • 각 단계에서 현재 유효한 창 j - i 1의 크기를 계산하고 maxBeauty를 업데이트합니다.

---

복잡성 분석:

1. 시간 복잡성:
   • 배열 정렬: O(n log n).
   • 슬라이딩 윈도우 순회: O(n).
   • 전체: O(n log n).
2. 공간 복잡성:
   • O(1), 솔루션은 몇 가지 추가 변수만 사용하기 때문입니다.

---

예:

입력 1:

$nums = [4, 6, 1, 2];
$k = 2;
echo maximumBeauty($nums, $k); // Output: 3

입력 2:

$nums = [1, 1, 1, 1];
$k = 10;
echo maximumBeauty($nums, $k); // Output: 4

이 솔루션은 제약 조건을 준수하고 대규모 입력에 대한 결과를 효율적으로 계산합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 작업 적용 후 배열의 최대 아름다움의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!