Leetcode 495

1072 단어 leetcode
이 문 제 는 중독 시간 서열 과 매번 독 이 얼마나 지속 되 는 지 에 따라 총 중독 시간 이 얼마 인지 계산한다.주로 두 가지 상황 으로 나 뉘 는데 하 나 는 중독 이 끝나 기 전에 다음 중독 이 오지 않 았 고 다른 하 나 는 중독 이 끝나 기 전에 새로운 중독 이 왔 다 는 것 이다.새로 온 중독 시간 이 point 라 고 가정 하면 전자의 전체 중독 시간 은 duration 을 더 해 야 하고 후 자 는 point - start 를 더 해 야 한다.또한 중독 이 끝 나 는 시간 과 중독 이 끝 나 는 시간 을 끊임없이 갱신 해 새로운 중독 이 올 때 중독 상태 에 있 는 지 판단 해 야 한다.알고리즘 복잡 도 는 O (n) 이 고 코드 는 다음 과 같 습 니 다.
class Solution(object):
    def findPoisonedDuration(self, timeSeries, duration):
        """
        :type timeSeries: List[int]
        :type duration: int
        :rtype: int
        """
        if len(timeSeries) == 0:
            return 0

        result = 0
        start = timeSeries[0]
        end = start + duration
        for i in range(1, len(timeSeries)):
            point = timeSeries[i]
            if point < end:
                result += point - start
            else:
                result += duration
            start = point
            end = start + duration
        result += duration
        return result

좋은 웹페이지 즐겨찾기