2012. Sum of Beauty in the Array (Medium)

양끝 값을 위치를 제외하고, 중간의 어떤 값이 

• 좌/우 보다 크면 1점
• 좌측의 모두보다 크고, 우측의 모두보다 작으면 2점

 

좌/우측의 비교는 O(N)으로 선형 탐색을 통해 찾고,

좌측모두보다 크고 우측 모두 보다 작은 것은

• 미리 만들어 놓은 max value list와 min value list를 사용
• 각각 만드는데 O(N)의 시간 소모

 

전체 알고리즘의 복잡도는 O(N)

 

mx = [0]*len(nums) mn = [0]*len(nums) mx[0] = nums[0] for i in range(1, len(nums)):     mx[i] = max(mx[i - 1], nums[i]) mn[-1] = nums[-1] for i in range(len(nums) - 2, -1, -1):     mn[i] = min(mn[i + 1], nums[i]) score = 0 for i in range(1, len(nums) - 1):     if nums[i - 1] < nums[i] < nums[i + 1]:         if mx[i - 1] < nums[i] < mn[i + 1]:             score += 2         else:             score += 1 return score