알고리즘 일기장 | LeetCode 239. 슬라이딩 창 최대 값

제목 설명
배열 nums 를 지정 합 니 다. k 크기 의 미끄럼 창 이 배열 의 맨 왼쪽 에서 배열 의 맨 오른쪽 으로 이동 합 니 다.미끄럼 창 k 에 있 는 숫자 만 볼 수 있 습 니 다.슬라이딩 창 은 매번 오른쪽으로 한 분만 이동 합 니 다.
슬라이딩 창의 최대 값 을 되 돌려 줍 니 다.
예시:

  : nums = [1,3,-1,-3,5,3,6,7],   k = 3
  : [3,3,5,5,6,7] 
  : 

                            
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

주의:
k 가 항상 유효 하 다 고 가정 할 수 있 습 니 다. 1 ≤ k ≤ 입력 배열 의 크기 이 고 입력 배열 이 비어 있 지 않 습 니 다.
진급:
당신 은 선형 시간 복잡 도 내 에서 이 문 제 를 해결 할 수 있 습 니까?
분석 해답
이것 은 로 표 시 된 제목 으로 얼핏 보면 선형 복잡 도와 배열 내용 의 동태 적 인 증감 이 있 는 것 을 발견 할 수 있다.이 문제 에 대응 하 는 라벨 은 이기 때문에 우 리 는 먼저 더미 로 해결 하 는 것 을 고려 합 니 다.최대 더 미 를 유지 하고 오른쪽으로 한 칸 씩 이동 할 때마다 최신 값 을 더 미 를 만 든 다음 최대 값 을 꺼 내 현재 창 에 있 는 지 판단 합 니 다.우 리 는 쓰레기 휴지통 으로 추가 계산 기 를 도입 할 수 있 습 니 다. 오른쪽으로 이동 할 때마다 가장 왼쪽 값 은 창 을 떠 납 니 다. 카운터 에서 이 값 의 수 를 하나 더 하면 휴지통 에 이 값 이 하나 더 있 음 을 나타 냅 니 다.그리고 최대 치 를 꺼 낼 때 휴지통 의 계수 가 0 인지, 0 이 아 닌 지 판단 하면 현재 이 최대 치 는 버 려 진 것 이 고 사용 할 수 없 음 을 나타 낸다. 해당 값 이 휴지통 에서 0 이 아 닐 때 까지 다음 최대 치 를 계속 꺼 내야 한다.이런 방법 은 한 번 에 옮 겨 다 니 기만 하면 되 지만 크기 가 * * k * 인 더 미 를 유지 해 야 한다. 매번 쌓 이 고 쌓 이 는 평균 시간 은 logk 이기 때문에 총 소모 시간 은 실제 O(Nlogk) 이다.비록 효율 이 좀 떨 어 졌 지만 직관 적 인 편 이다. 코드 는 다음 과 같다.

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        import heapq
        from collections import defaultdict

        if not nums:
            return []

        nums = [-1 * x for x in nums]
        counter = defaultdict(int)

        windows = nums[:k]
        res = []
        heapq.heapify(windows)
        res.append(-1 * windows[0])
        counter[nums[0]] += 1
        for i in range(len(nums) - k):
            heapq.heappush(windows, nums[i + k])
            min_num = windows[0]
            while counter[min_num] > 0:
                counter[min_num] -= 1
                heapq.heappop(windows)
                min_num = windows[0]
            res.append(-1 * min_num)
            counter[nums[i + 1]] += 1

        return res

효율 을 한층 높이 기 위해 서 는 창문 이 미 끄 러 질 때 무슨 일이 일 어 났 는 지 더욱 세밀 하 게 살 펴 볼 수 있다.우선 긍정 적 인 점 은 이전 창 에서 가장 왼쪽 값 을 제거 해 야 합 니 다.새로 추 가 된 창의 값 에 대해 a 로 기록 합 니 다. 창 에 작은 값 이 있다 면 이 창 부터 창의 최대 값 은 이 값 이 아 닐 것 입 니 다. 따라서 창 에 남 은 모든 값 이 a 보다 작 지 않 을 때 까지 창 에서 제거 할 수 있 습 니 다.이런 방법 에 따라 창 안의 임의의 시간 에 남 은 값 은 반드시 단 조 롭 고 점차 줄 어드 는 서열 일 것 이다. 우 리 는 쌍 단 대기 열 을 통 해 이런 조작 을 실현 할 수 있다.코드 구현 은 다음 과 같 습 니 다.

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        from collections import deque

        res = []
        q = deque()
        for idx, v in enumerate(nums):
            if len(q) > 0 and q[0] <= idx - k:
                t = q.popleft()
            while len(q) > 0 and nums[q[-1]] < v:
                q.pop()
            q.append(idx)
            if idx >= k - 1:
                res.append(nums[q[0]])

        return res

이러한 해법 에서 모든 요 소 는 최대 두 번 방문 되 고 매번 방문 할 때마다 상수 작업 이기 때문에 복잡 도 는 O(N) 로 제어 할 수 있다.제출 한 결 과 를 보면 시간 소모 도 이전 방법 보다 확실히 좋다.다만 상대 적 으로 전체 과정 에 대한 심도 있 는 분석 이 필요 하기 때문에 이해 하기 어 려 울 수도 있다.또 질문 이 있 으 면 댓 글 에 댓 글 을 달 아 소통 할 수 있 습 니 다.
오늘 의 나 눔 은 여기까지 입 니 다. 나중에 뵙 겠 습 니 다.
이상 은 본문의 모든 내용 입 니 다. 이 글 을 좋아 하신 다 면 친구 들 에 게 공유 해 주 십시오.
읽 어 주 셔 서 감사합니다. 즐 거 운 생활 되 세 요!
작자: 샤 오미 형 2019 - 03 - 21