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

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

난이도:어려움

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

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

• arr.length >= 3
• 0 < 나는 < arr.length - 1 다음과 같습니다. arr[0] < arr[1] < ... < arr[i - 1] < 도착[i]
  • 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 <= nums.length <= 1000
  • 1 <= 숫자[i] <= 10
  9
  • 숫자로 산 배열을 만들 수 있다는 것은 보장됩니다.
  힌트:
  최대 산 하위 시퀀스를 제거하려면 최소 요소 대신 반대 방향을 생각하세요
  1. LIS를 생각하면 좀 가까운 것 같아요
  해결책:

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

  최대 산 부분 수열

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

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

     :

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

     :

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

  3. 최대 산 길이 계산:

     • 각 인덱스 i에 대해 0 < 나는 < n - 1, 유효한 피크가 있는지 확인합니다(예: leftLIS[i] > 1 및 rightLIS[i] > 1). i에서 산의 길이를 leftLIS[i] rightLIS[i] - 1로 계산합니다.

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

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

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

  
  
  
  
  
  
    
    
    설명:
  
  
  
  
  왼쪽 LIS 계산:
  
  
  
  leftLIS[i]는 i에서 끝나는 증가하는 부분 수열의 최대 길이를 저장합니다. 각 i를 반복하고, 각 i에 대해 0부터 i-1까지 반복하여 i에서 끝나는 가장 긴 하위 시퀀스를 찾습니다.
  
  
  
  올바른 LIS 계산:
  
  
  
  rightLIS[i]는 i에서 시작하여 감소하는 부분 수열의 최대 길이를 저장합니다. n-2에서 0까지 역방향으로 반복하고, 각 i에 대해 n-1에서 i 1까지 반복하여 i에서 시작하는 가장 긴 부분 수열을 찾습니다.
  
  
  
  산 계산:
  
  
  인덱스 i의 유효한 피크는 왼쪽LIS[i] > 1이고 오른쪽LIS[i] > 1. i에 봉우리가 있는 산의 길이는 왼쪽LIS[i] 오른쪽LIS[i] - 1.
  
  
  
  최종 계산:
  
  
  필요한 최소 제거량은 원래 배열 길이와 발견된 최대 산 길이의 차이입니다.
  
  
  
  
  
    
    
    복잡성 분석
  
  
  
  
  시간 복잡도: O(n2), LIS 계산의 이중 루프로 인해 발생합니다.
  
  공간 복잡성: O(n), leftLIS 및 rightLIS 배열 저장용.
  
  
  이 솔루션을 사용하면 최대 산 하위 순서를 찾고 산 배열을 달성하는 데 필요한 최소 제거량을 계산할 수 있습니다.
  
  연락처 링크
  
  이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
  
  이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
  
  
  링크드인
  깃허브
  
  
  
            
  
              
    
  
              
          
  위 내용은 마운틴 배열을 만들기 위한 최소 제거 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!