. 최대 폭 램프

962. 최대 너비 램프

난이도:중

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

정수 배열 nums의 ramp는 i < j 및 nums[i] <= nums[j]. 이러한 램프의 너비는 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 <= nums.length <= 5 * 10⁴
• 0 <= 숫자[i] <= 5 * 10⁴

해결책:

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

접근하다:

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

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

  
  
  설명:




감소 스택 생성:


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



끝에서 횡단:


배열을 뒤로 이동하면서 각 j에 대해 nums[i] <= nums[j]만큼 스택에서 인덱스 i를 팝합니다.
너비 j - i를 계산하고 maxWidth를 업데이트합니다.



이것이 효과적인 이유:


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



시간 복잡성:


각 인덱스가 한 번 푸시되므로 스택을 구축하는 데 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!