연속 하위 배열-PHP 튜토리얼-php.cn

연속 하위 배열

Mary-Kate Olsen

풀어 주다： 2024-12-25 05:46:15

원래의

830명이 탐색했습니다.

Continuous Subarrays

2762. 연속 하위 배열

난이도:중

주제: 슬라이딩 윈도우, 배열, 순서 집합, 힙(우선 순위 큐), 큐, 단조 큐, 두 포인터, 순서 맵, 해시 테이블, 동적 프로그래밍, 계산, 수학, 이진 검색 트리, 세그먼트 트리, 트리, 스택, 이진 검색, 단조 스택, 메모이제이션, 반복자, 탐욕, 깊이 우선 검색, 재귀

인덱스가 0인 정수 배열 숫자가 제공됩니다. 다음과 같은 경우 숫자의 하위 배열을 연속형이라고 합니다.

i, i 1, ..., j를 하위 배열의 인덱스로 둡니다. 그런 다음 각 인덱스 쌍에 대해 i <= i₁, i₂ <= j, 0 <= |nums[i₁] - 숫자[i₂]| <= 2.

연속 하위 배열의 총 개수를 반환합니다.

하위 배열은 배열 내 연속된 비어 있지 않은 요소 시퀀스입니다.

예 1:

입력: 숫자 = [5,4,2,4]
출력: 8
설명:
- 크기 1의 연속 하위 배열: [5], [4], [2], [4].
- 크기 2의 연속 하위 배열: [5,4], [4,2], [2,4].
- 크기 3의 연속 하위 배열: [4,2,4].
- 크기 4의 하위 배열이 없습니다.
- 총 연속 하위 배열 = 4 3 1 = 8.
- 더 이상 연속된 하위 배열이 없음을 알 수 있습니다.

예 2:

입력: 숫자 = [1,2,3]
출력: 6
설명:
- 크기 1의 연속 하위 배열: [1], [2], [3].
- 크기 2의 연속 하위 배열: [1,2], [2,3].
- 크기 3의 연속 하위 배열: [1,2,3].
- 총 연속 하위 배열 = 3 2 1 = 6.

제약조건:

1 <= nums.length <= 10⁵
1 <= 숫자[i] <= 10⁹

힌트:

슬라이딩 윈도우 기법을 사용해 보세요.
세트나 맵을 사용하여 하위 배열의 최대값과 최소값을 추적하세요.

해결책:

슬라이딩 윈도우 기술을 사용하여 연속 하위 배열의 수를 효율적으로 계산할 수 있습니다. 하위 배열의 최대값과 최소값의 차이가 최대 2인 유효한 창을 유지합니다. 현재 창 내에서 최대값과 최소값을 효율적으로 추적하기 위해 두 개의 deque(하나)를 사용할 수 있습니다. 최대값과 최소값 중 하나).

접근하다

왼쪽과 오른쪽의 두 포인터를 사용하는 슬라이딩 창 기술을 사용하세요.
두 개의 데크 사용:
- 최대값에 대한 요소의 인덱스를 내림차순으로 추적하는 것입니다.
- 최소값에 대한 요소의 인덱스를 오름차순으로 추적하는 것입니다.
각 색인 권한에 대해:
- 현재 창을 반영하도록 데크를 업데이트하세요.
- 창이 유효한 상태로 유지되는지 확인하세요(최대값과 최소값의 차이 ≤ 2). 유효하지 않은 경우 왼쪽 포인터를 증가시켜 창을 축소하세요.
- 오른쪽 인덱스에서 끝나는 유효한 하위 배열의 수를 (오른쪽 - 왼쪽 1)로 계산합니다.
하위 배열의 총 개수를 반환합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2762. 연속 하위 배열

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

// Example usage
$nums1 = [5, 4, 2, 4];
echo continuousSubarrays($nums1) . "\n"; // Output: 8

$nums2 = [1, 2, 3];
echo continuousSubarrays($nums2) . "\n"; // Output: 6
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li><p><strong>슬라이딩 창:</strong><br><br>
왼쪽 포인터는 창이 유효하지 않은 경우에만 앞으로 이동합니다(즉, 최대값과 최소값의 차이가 2를 초과하는 경우). 오른쪽 포인터는 배열을 반복하여 창을 확장합니다.</p></li>
<li>
<p><strong>최대 및 최소값에 대한 Deque:</strong></p>

<ul>
<li>maxDeque는 항상 요소의 인덱스를 내림차순으로 유지하여 현재 창의 최대값이 맨 앞에 오도록 합니다(maxDeque[0]).</li>
<li>minDeque는 항상 요소의 인덱스를 오름차순으로 유지하여 현재 창의 최소값이 맨 앞에 오도록 합니다(minDeque[0]).</li>
</ul>
</li>
<li><p><strong>하위 배열 계산:</strong><br><br>
왼쪽에서 오른쪽으로 모든 하위 배열이 유효하므로 각 오른쪽에 대해 오른쪽에서 끝나는 유효한 하위 배열의 수는 (오른쪽 - 왼쪽 1)과 같습니다.</p></li>
<li><p><strong>효율성:</strong><br><br>
각 요소는 데크에 최대 한 번 추가되고 제거되므로 시간 복잡도가 <strong>O(n)</strong>이 됩니다. 데크 때문에 공간 복잡도는 <strong>O(n)</strong>입니다.</p></li>
</ol>


<hr>

<h3>
  
  
  산출
</h3>



<pre class="brush:php;toolbar:false">8
6

로그인 후 복사