1637-kir3i.md

1637. Widest Vertical Area Between Two Points Containing No Points

Solution

• 시간복잡도: O(NlogN)

• 알고리즘

  구현, 스위핑

• 풀이설명

  1. 먼저 필요한 정보는 x좌표 뿐이므로 points에서 x좌표 정보만 뽑아낸 리스트인 xs를 만듭니다. 그리고 각 점들간 거리를 계산하기 위해 정렬합니다.
  2. 각 점들 사이의 거리를 계산하여 최댓값을 구합니다.

• 소스코드

class Solution:
    def maxWidthOfVerticalArea(self, points):
        xs = sorted([x for x, y in points])
        
        ans = 0
        for i in range(len(xs) - 1):
            ans = max(ans, xs[i+1] - xs[i])

        return ans