Python에서 최대 너비 램프를 찾는 프로그램

<시간/>

배열 nums가 있다고 가정하고 램프는 i

따라서 입력이 nums =[6,0,8,2,1,5]와 같으면 최대 너비 램프가 (i, j) =(1, 5) 및 nums에서 달성되기 때문에 출력은 4가 됩니다. [1] =0 및 숫자[5] =5.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

B :=새 지도
범위 0에서 숫자 크기까지의 i에 대해
- x :=숫자[i]
- x가 B에 있으면
  - B[x]
    끝에 i 삽입
- 그렇지 않으면
  - B[x] :=[i]
mini :=목록은 처음에 하나의 f를 저장
maxi :=목록은 처음에 하나의 -inf를 저장합니다.
B의 모든 키 목록을 정렬하는 각 x에 대해 수행
- mini의 마지막 요소의 최소값과 mini의 끝에 B[x]의 최소값 삽입
B의 모든 키의 역순으로 정렬된 목록의 각 x에 대해 수행
- mini의 마지막 요소의 최소값과 mini의 끝에 B[x]의 최소값 삽입
maxi :=maxi를 역으로 한 다음 시작에서 두 번째 마지막 요소까지 하위 배열을 가져옵니다.
mini :=mini의 하위 배열[인덱스 1에서 끝까지]
피 :=0
res :=-inf
동안 p <미니의 크기, do
- res :=최대 res 및 (maxi[p] - mini[p])
- 피 :=피 + 1
반환 해상도

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(nums):
   B = {}
   for i in range(len(nums)):
      x = nums[i]
      if x in B:
         B[x].append(i)
      else:
         B[x] = [i]

   mini = [float('inf')]
   maxi = [float('-inf')]
   for x in sorted(B.keys()):
      mini.append(min(mini[-1], min(B[x])))

   for x in sorted(B.keys(), reverse = True):
      maxi.append(max(maxi[-1], max(B[x])))

   maxi = maxi[::-1][:-1]
   mini = mini[1:]

   p = 0
   res = float('-inf')
   while p < len(mini):
      res = max(res, maxi[p] - mini[p])
      p += 1

   return res

nums = [6,0,8,2,1,5]
print(solve(nums))

입력

[6,0,8,2,1,5]