다른 건물의 높이 목록이 있다고 가정합니다. 높이 값 높이[i]를 가진 건물은 오른쪽에 있는 모든 건물이 해당 건물보다 짧을 때 바다를 볼 수 있습니다. 바다가 보이는 곳에서 건물 인덱스를 오름차순으로 찾아야 합니다.
따라서 입력이 height =[8, 12, 12, 9, 10, 6]과 같으면 출력은 [2, 4, 5]가 됩니다. 인덱스 2의 건물 높이 12에서 바다를 볼 수 있기 때문입니다. 색인 10에서 건물 높이 10, 색인 5에서 마지막 건물에서.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 스택 :=새 목록
- 높이의 각 인덱스 idx 및 높이 h에 대해 다음을 수행합니다.
- 스택이 비어 있지 않고 height[스택 상단] <=h, do
- 동안
- 스택에서 마지막 요소 삭제
- 스택이 비어 있지 않고 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]