마운틴 배열을 만들기 위한 최소 제거 수

1671. 산 배열을 만들기 위한 최소 제거 수

난이도:어려움

주제: 배열, 이진 검색, 동적 프로그래밍, Greedy

다음과 같은 경우에만 배열 arr이 산형 배열임을 기억하실 수 있습니다.

• arr.length >= 3
• 0 arr[0]
• arr[i] > arr[i 1] > ... > arr[arr.length - 1]

정수 배열 nums가 주어지면 nums를

산 배열으로 만들기 위해 제거할 최소 요소 수를 반환합니다.

예 1:

입력:
• 숫자 = [1,3,1]
출력:
• 0
설명:
• 배열 자체가 산 배열이므로 어떤 요소도 제거할 필요가 없습니다.

예 2:

입력:
• 숫자 = [2,1,1,5,6,2,3,1]
출력:
• 3
설명:
• 한 가지 해결책은 인덱스 0, 1, 5의 요소를 제거하여 배열 nums = [1,5,6,3,1]을 만드는 것입니다.

제약조건:

3

1 9

숫자로 산 배열을 만들 수 있다는 것은 보장됩니다.

힌트:

최대 산 하위 시퀀스를 제거하려면 최소 요소 대신 반대 방향을 생각하세요

1. LIS를 생각하면 좀 가까운 것 같아요

해결책:

제거할 요소를 직접 계산하는 대신

최대 산 부분 수열

을 찾는 아이디어로 동적 프로그래밍 접근 방식을 사용할 수 있습니다. 이 접근 방식은 배열의 각 위치에 대해 두 개의 LIS(최장 증가 부분 시퀀스)를 찾는 것을 기반으로 합니다. 하나는 왼쪽에서 오른쪽으로 가고 다른 하나는 오른쪽에서 떠났다. 가능한 가장 긴 산 하위 시퀀스가 ​​있으면 원래 배열 길이와 이 하위 시퀀스 길이의 차이로 제거할 최소 요소가 제공됩니다. 솔루션 개요

1. 증가하는 하위 시퀀스 길이 식별

   :

   leftLIS 배열을 계산합니다. 여기서 leftLIS[i]는 i에서 끝나는(왼쪽에서 오른쪽으로) 가장 긴 증가 부분 수열의 길이를 나타냅니다.
2. 감소하는 하위 시퀀스 길이 식별

   :

   • rightLIS 배열을 계산합니다. 여기서 rightLIS[i]는 i에서 시작하여(오른쪽에서 왼쪽으로) 가장 긴 감소 부분 수열의 길이를 나타냅니다.

3. 최대 산 길이 계산:

   • 각 인덱스 i에 대해 0 1 및 rightLIS[i] > 1). i에서 산의 길이를 leftLIS[i] rightLIS[i] - 1로 계산합니다.

4. 최소한의 제거를 받으세요:

   • 제거할 최소 요소는 원래 배열 길이에서 발견된 가장 긴 산 길이를 뺀 값입니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1671. 산 배열을 만들기 위한 최소 제거 수

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

// Example usage
$nums1 = [1, 3, 1];
echo minimumMountainRemovals($nums1); // Output: 0

$nums2 = [2, 1, 1, 5, 6, 2, 3, 1];
echo minimumMountainRemovals($nums2); // Output: 3
?>

설명:

1. 왼쪽 LIS 계산:

   • leftLIS[i]는 i에서 끝나는 증가하는 부분 수열의 최대 길이를 저장합니다. 각 i를 반복하고, 각 i에 대해 0부터 i-1까지 반복하여 i에서 끝나는 가장 긴 하위 시퀀스를 찾습니다.

2. 올바른 LIS 계산:

   • rightLIS[i]는 i에서 시작하여 감소하는 부분 수열의 최대 길이를 저장합니다. n-2에서 0까지 역방향으로 반복하고, 각 i에 대해 n-1에서 i 1까지 반복하여 i에서 시작하는 가장 긴 부분 수열을 찾습니다.

3. 산 계산:

   • 인덱스 i의 유효한 피크는 왼쪽LIS[i] > 1이고 오른쪽LIS[i] > 1. i에 봉우리가 있는 산의 길이는 왼쪽LIS[i] 오른쪽LIS[i] - 1.

4. 최종 계산:

   • 필요한 최소 제거량은 원래 배열 길이와 발견된 최대 산 길이의 차이입니다.

복잡성 분석

• 시간 복잡도: O(n²), LIS 계산의 이중 루프로 인해 발생합니다.
• 공간 복잡성: O(n), leftLIS 및 rightLIS 배열 저장용.

이 솔루션을 사용하면 최대 산 하위 순서를 찾고 산 배열을 달성하는 데 필요한 최소 제거량을 계산할 수 있습니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 마운틴 배열을 만들기 위한 최소 제거 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!