. 정렬할 최대 청크

769. 정렬할 최대 청크

난이도:중

주제: 배열, 스택, 탐욕, 정렬, 단조 스택

[0, n - 1] 범위의 정수 순열을 나타내는 n 길이의 정수 배열 arr이 제공됩니다.

arr을 몇 개의 청크(즉, 파티션)로 분할하고 각 청크를 개별적으로 정렬합니다. 이들을 연결한 후 결과는 정렬된 배열과 같아야 합니다.

배열을 정렬하기 위해 만들 수 있는 최대 청크 수를 반환합니다.

예 1:

• 입력: arr = [4,3,2,1,0]
• 출력: 1
• 설명:
  • 두 개 이상의 청크로 분할하면 필요한 결과가 반환되지 않습니다.
  • 예를 들어 [4, 3], [2, 1, 0]으로 분할하면 [3, 4, 0, 1, 2]가 되어 정렬되지 않습니다.

예 2:

• 입력: arr = [1,0,2,3,4]
• 출력: 4
• 설명:
  • [1, 0], [2, 3, 4]와 같이 두 개의 덩어리로 나눌 수 있습니다.
  • 단, [1, 0], [2], [3], [4]로 분할하는 것이 가능한 최대 청크 수입니다.

제약조건:

• n == arr.length
• 1
• 0 <= arr[i] < ㄴ
• arr의 모든 요소는 독특합니다.

힌트:

1. 첫 번째 청크는 A[:k 1] == [0, 1, 2, ...k];에 대한 가장 작은 k로 찾을 수 있습니다. 그런 다음 이 과정을 반복합니다.

해결책:

각 청크를 개별적으로 정렬할 수 있도록 형성할 수 있는 가장 많은 청크 수를 찾아야 하며, 연결하면 전체 배열이 정렬된 버전이 됩니다.

접근하다:

1. 주요 관찰:

   • 배열은 0부터 n-1까지의 정수 순열입니다. 배열을 순회하면서 청크가 분리될 수 있는 위치를 찾는 것이 아이디어입니다.
   • 청크 내의 모든 인덱스에 대해 해당 지점까지의 최대 요소가 원래 정렬된 배열에서 해당 지점 이후의 최소 요소를 초과하지 않는 경우 청크를 정렬할 수 있습니다.

2. 전략:

   • 왼쪽에서 오른쪽으로 이동하면서 만나는 최대값을 추적하세요.
   • 각 인덱스 i에서 i까지의 최대값이 i보다 작거나 같은지 확인합니다. 이 조건이 성립하면 왼쪽 부분을 독립적으로 정렬할 수 있으므로 해당 인덱스에서 배열을 분할할 수 있다는 의미입니다.

3. 단계:

   • 실행 최대값을 유지하면서 배열을 반복합니다.
   • 실행 최대값이 현재 인덱스와 같을 때마다 청크가 만들어질 수 있습니다.
   • 이러한 덩어리의 수를 세어보세요.

이 솔루션을 PHP로 구현해 보겠습니다. 769. 정렬할 최대 청크

  
  
  설명:




초기화:


maxSoFar = -1로 시작하여 배열을 탐색할 때 배열의 최대값을 올바르게 추적하는지 확인합니다.

Chunks = 0은 형성될 수 있는 청크 수를 추적합니다.



루프:


배열의 각 요소를 반복합니다.
각 요소에 대해 maxSoFar를 현재 요소와 이전에 확인된 최대값 사이의 최대값으로 업데이트합니다.
maxSoFar == i인 경우 인덱스 i까지의 배열이 독립적으로 정렬될 수 있으며 이것이 유효한 청크임을 의미합니다.
이 조건이 충족될 때마다 청크 수를 늘립니다.



반품:


마지막으로 총 청크 수가 반환됩니다.





  
  
  시간 복잡도:




시간 복잡도: O(n), 여기서 n은 배열의 길이입니다. 우리는 어레이를 한 번만 통과합니다.

공간 복잡성: O(1), 중간 결과를 저장하기 위해 몇 가지 변수만 사용하기 때문입니다.



  
  
  예제 연습:


arr = [1, 0, 2, 3, 4]의 경우:


인덱스 0에서 지금까지 발견된 최대값은 1입니다. 여기서는 분할할 수 없습니다.
인덱스 1에서 최대값은 1로 현재 인덱스 1과 일치하므로 청크로 분할할 수 있습니다.
인덱스 2에서 최대값은 2이고, 인덱스 2와 일치하므로 다시 분할합니다.
인덱스 3에서 최대값은 3이고, 인덱스 3과 일치하므로 다시 분할합니다.
인덱스 4에서 최대값은 4이고, 인덱스 4와 일치하므로 다시 분할합니다.


따라서 이 경우의 출력은 4개 청크로 분할할 수 있으므로 4입니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 . 정렬할 최대 청크의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!