배열을 정렬하기 위해 제거할 가장 짧은 하위 배열

1574. 배열 정렬을 위해 제거할 최단 하위 배열

난이도:중

주제: 배열, 두 포인터, 이진 검색, 스택, 단조 스택

정수 배열 arr이 주어지면 arr의 나머지 요소가 감소하지 않도록.

arr에서 하위 배열(비어 있을 수 있음)을 제거합니다.

제거할 가장 짧은 하위 배열의 길이를 반환합니다.

하위 배열은 배열의 연속된 하위 시퀀스입니다.

예 1:

• 입력: arr = [1,2,3,10,4,2,3,5]
• 출력: 3
• 설명: 제거할 수 있는 가장 짧은 하위 배열은 길이가 3인 [10,4,2]입니다. 그 뒤의 나머지 요소는 정렬된 [1,2,3,3,5]입니다.
  • 또 다른 올바른 해결책은 하위 배열 [3,10,4]을 제거하는 것입니다.

예 2:

• 입력: arr = [5,4,3,2,1]
• 출력: 4
• 설명: 배열이 엄격하게 감소하므로 단일 요소만 유지할 수 있습니다. 따라서 길이가 4인 [5,4,3,2] 또는 [4,3,2,1] 하위 배열을 제거해야 합니다.

예 3:

• 입력: arr = [1,2,3]
• 출력: 0
• 설명: 배열이 이미 감소하지 않습니다. 어떤 요소도 제거할 필요가 없습니다.

제약조건:

• 1 <= arr.length <= 10⁵
• 0 <= arr[i] <= 10⁹

힌트:

1. 핵심은 각각 첫 번째 요소로 시작하거나 마지막 요소로 끝나는 감소하지 않는 가장 긴 하위 배열을 찾는 것입니다.
2. 일부 하위 배열을 제거한 후 결과는 정렬된 접두어와 정렬된 접미어의 연결입니다. 여기서 접두사의 마지막 요소는 접미사의 첫 번째 요소보다 작습니다.

해결책:

정렬 및 이진 검색 기술을 사용할 수 있습니다. 계획은 다음과 같습니다.

접근하다:

1. 두 가지 지침 접근 방식:

   • 먼저 감소하지 않는 가장 긴 접두사(왼쪽 포인터)를 식별합니다.
   • 그런 다음 감소하지 않는 가장 긴 접미사(오른쪽 포인터)를 식별합니다.
   • 이후에는 배열의 중간 부분을 고려하여 결합된 배열이 감소하지 않도록 제거할 하위 배열을 조정하여 이 두 하위 배열을 결합해 보세요.

2. 단조 스택:

   • 단조 스택을 사용하면 정렬된 방식으로 하위 배열 요소를 관리할 수 있습니다.

3. 단계:

   • 감소하지 않는 가장 긴 접두사를 찾습니다(왼쪽).
   • 가장 긴 비감소 접미사를 찾아보세요(오른쪽).
   • 유효한 조합을 형성할 수 있는 요소를 찾아 두 하위 배열을 병합해 보세요.

4. 최적화:

   • 이진 검색을 사용하여 제거할 가장 작은 하위 배열을 찾기 위한 병합 단계를 최적화하세요.

PHP에서 이 솔루션을 구현해 보겠습니다: 1574. 배열 정렬을 위해 제거할 최단 하위 배열

  
  
  설명:




감소하지 않는 가장 긴 접두사 및 접미사:


접두사는 요소가 감소하지 않는 순서가 될 때까지 배열을 처음부터 순회하여 결정됩니다.
마찬가지로 접미사는 끝에서부터 순회하여 결정됩니다.



최소 초기 제거:


접두사 또는 접미사만 유지하여 제거 길이를 계산합니다.



접두사 및 접미사 병합:


접두사의 마지막 요소가 접미사의 첫 번째 요소보다 작거나 같도록 두 개의 포인터(접두사의 경우 i, 접미사의 경우 j)를 사용하여 제거할 가장 작은 하위 배열을 찾습니다.



반품 결과:


결과는 제거할 하위 배열의 최소 길이이며, 초기 제거 길이나 접두사와 접미사 병합 길이 중 더 작은 길이로 계산됩니다.





  
  
  복잡성




시간 복잡도: O(n), 배열이 최대 두 번 탐색되기 때문입니다.

공간 복잡도: O(1), 소수의 변수만 사용하므로


이 솔루션은 2포인터 기술을 사용하여 배열을 정렬하기 위해 제거할 가장 짧은 하위 배열을 효율적으로 찾고, 최대 10^5 요소 제약 조건까지 큰 배열을 처리합니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 배열을 정렬하기 위해 제거할 가장 짧은 하위 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!