. 최대 폭 램프

962. 최대 너비 램프

난이도:중

주제: 배열, 스택, 단조 스택

정수 배열 nums의 ramp는 i 너비는 j - i입니다.

정수 배열 nums가 주어지면 램프의 최대 너비를 nums로 반환합니다. 숫자에 ramp가 없으면 0을 반환합니다.

예 1:

• 입력: 숫자 = [6,0,8,2,1,5]
• 출력: 4
• 설명: 최대 너비 램프는 (i, j) = (1, 5)에서 달성됩니다. nums[1] = 0 및 nums[5] = 5.

예 2:

• 입력: 숫자 = [9,8,1,0,1,9,4,0,4,1]
• 출력: 7
• 설명: 최대 너비 램프는 (i, j) = (2, 9)에서 달성됩니다. nums[2] = 1 및 nums[9] = 1.

제약조건:

• 2 4
• 0 4

해결책:

단조 스택 개념을 활용할 수 있습니다. 해결책과 설명은 다음과 같습니다.

접근하다:

1. 단조 감소 스택: nums[stack[i]]가 감소하는 방식으로 요소의 인덱스를 추적하는 스택을 만듭니다. 이를 통해 나중에 nums[i] 인 쌍 (i, j)를 찾을 수 있습니다.
2. 끝에서 탐색: 스택을 생성한 후 끝에서 배열을 탐색하여(j에서 n-1부터 0까지) 각 j에 대해 가장 먼 i를 찾습니다. 여기서 nums[i]
3. 최대 너비 업데이트: 스택의 현재 상단에 대해 nums[i]

이 솔루션을 PHP로 구현해 보겠습니다: 962. 최대 너비 램프

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

// Example 1
$nums = [6, 0, 8, 2, 1, 5];
echo maxWidthRamp($nums);  // Output: 4

// Example 2
$nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1];
echo maxWidthRamp($nums);  // Output: 7
?>

설명:

1. 감소 스택 생성:

   • 배열을 반복하고 스택에 인덱스를 추가합니다.
   • 스택의 마지막 인덱스 값보다 작거나 같은 값에 해당하는 경우에만 인덱스를 추가하세요. 이렇게 하면 스택의 값이 내림차순으로 유지됩니다.

2. 끝에서 횡단:

   • 배열을 뒤로 이동하면서 각 j에 대해 nums[i]
   • 너비 j - i를 계산하고 maxWidth를 업데이트합니다.

3. 이것이 효과적인 이유:

   • 감소하는 인덱스 스택을 유지함으로써 더 큰 값을 가진 j를 만날 때 i가 스택에서 팝될 때 더 큰 너비 j - i를 제공할 수 있습니다.

4. 시간 복잡성:

   • 각 인덱스가 한 번 푸시되므로 스택을 구축하는 데 O(n) 시간이 걸립니다.
   • 끝에서 순회하고 인덱스를 팝하는 데에도 O(n)이 소요됩니다. 각 인덱스는 최대 한 번만 팝되기 때문입니다.
   • 전체적으로 솔루션은 O(n) 시간 내에 실행되며 이는 최대 5 * 10^4의 입력 크기에 효율적입니다.

산출:

• nums = [6, 0, 8, 2, 1, 5]의 경우 출력은 램프(1, 5)에 해당하는 4입니다.
• nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1]의 경우 출력은 램프(2, 9)에 해당하는 7입니다.

연락처 링크

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

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

• 링크드인
• 깃허브

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