Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

파이썬에서 바다가 보이는 곳에서 건물을 찾는 프로그램

<시간/>

다른 건물의 높이 목록이 있다고 가정합니다. 높이 값 높이[i]를 가진 건물은 오른쪽에 있는 모든 건물이 해당 건물보다 짧을 때 바다를 볼 수 있습니다. 바다가 보이는 곳에서 건물 인덱스를 오름차순으로 찾아야 합니다.

따라서 입력이 height =[8, 12, 12, 9, 10, 6]과 같으면 출력은 [2, 4, 5]가 됩니다. 인덱스 2의 건물 높이 12에서 바다를 볼 수 있기 때문입니다. 색인 10에서 건물 높이 10, 색인 5에서 마지막 건물에서.

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

  • 스택 :=새 목록
  • 높이의 각 인덱스 idx 및 높이 h에 대해 다음을 수행합니다.
    • 스택이 비어 있지 않고 height[스택 상단] <=h, do
        동안
      • 스택에서 마지막 요소 삭제
  • idx를 스택에 푸시
  • 반환 스택

예시

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

def solve(heights):
   stack = []
   for idx, h in enumerate(heights):
      while stack and heights[stack[-1]] <= h:
         stack.pop()
      stack.append(idx)
   return stack

heights = [8, 12, 12, 9, 10, 6]
print(solve(heights))

입력

[8, 12, 12, 9, 10, 6]

출력

[2, 4, 5]