Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

문제 번호, 이름: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

문제 링크: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/

날짜: 2024/06/23

상태: 완료

 

이 문제를 고른 이유

리트코드 오늘의문제

문제 보고 처음 든 생각

array sliding window 문제좀 그만 풀고 싶다 풀리지도 않는데..

N<=10^5 니까 N이나 NlogN 풀이를 생각해야 한다

 

풀이 v1

• 소요 시간 ?

import heapq
# python heapq only supports minheap



class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        answer = 1
        len_nums = len(nums)
        maxheap = []
        minheap = []

        minidx = 0
        maxidx = 0
        heapq.heappush(minheap, nums[minidx])
        heapq.heappush(maxheap, -nums[maxidx])

        while True:
            targetidx = maxidx + 1
            if targetidx >= len_nums:
                break
            minval = heapq.nsmallest(1, minheap)[0]
            maxval = -1 * heapq.nsmallest(1, maxheap)[0]

            if abs(minval - nums[targetidx]) <= limit and abs(maxval - nums[targetidx]) <= limit:
                maxidx += 1
                heapq.heappush(minheap, nums[targetidx])
                heapq.heappush(maxheap, -nums[targetidx])
            else:
                maxidx += 1
                heapq.heappushpop()??
                minidx += 1


        return answer

 

• 뭔가 subarray의 min과 max를 관리하면서 새 원소를 받았을 때 min, max와의 차가 limit 이하면 잘 추가하고, 아니라면 앞의 원소를 삭제하는 sliding window 방법을 생각했다. 시간복잡도를 많이 키우지 않으면서 min, max를 관리하는 방법으로 minheap, maxheap을 선택했다. 잘 되어가고 있었는데? 중간에 생각해보니 min, max가 아닌 그냥 특정 원소를 삭제해야 할 필요가 있더라. 그래서 멘붕하고 일단 여기까지를 정리 중

풀이 v2

• 소요 시간 대충 40분?

import heapq
# python heapq only supports minheap


class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        answer = 1
        len_nums = len(nums)
        maxheap = []
        minheap = []
        deleted = set()

        minidx = 0
        maxidx = 0
        heapq.heappush(minheap, (nums[minidx], minidx))
        heapq.heappush(maxheap, (-nums[maxidx], maxidx))

        while True:
            answer = max(answer, maxidx - minidx + 1)
            targetidx = maxidx + 1
            if targetidx >= len_nums:
                break
            while True:
                minval_candidate = minheap[0]
                if minval_candidate in deleted:
                    heapq.heappop(minheap)
                else:
                    minval = minheap[0][0]
                    break
            while True:
                maxval_candidate = maxheap[0]
                if (-maxval_candidate[0], maxval_candidate[1]) in deleted:
                    heapq.heappop(maxheap)
                else:
                    maxval = -maxheap[0][0]
                    break

            if abs(minval - nums[targetidx]) <= limit and abs(maxval - nums[targetidx]) <= limit:
                maxidx += 1
                heapq.heappush(minheap, (nums[targetidx], targetidx))
                heapq.heappush(maxheap, (-nums[targetidx], targetidx))
            else:
                deleted.add((nums[minidx], minidx))
                minidx += 1
                if minidx > maxidx:
                    maxidx += 1
                    heapq.heappush(minheap, (nums[targetidx], targetidx))
                    heapq.heappush(maxheap, (-nums[targetidx], targetidx))

        return answer

 

진짜 누더기 코드다

그래도 leetcode가 heapq library 사용을 허용해서 다행이었다
풀이 v1 에서 방향을 크게 틀어야 할 것 같았는데 다른 방향들도 생각해봤지만 답이 안 나와서 결국 v1에다가 삭제된 원소들을 관리하는 set을 하나 더 둬서 heap에서 pop을 해 봤는데 이미 삭제된 원소라면 그 원소를 무시하고 다시 pop 하도록 했다 

 

이러면 sliding window 탐색에 O(N) 시간, 각 윈도우에서 heap 처리가 O(logN)시간, delete 원소 관리도 O(logN) 시간 아마도? set이니까? 잘모룸 O(1)인가.. 여튼 대세에 지장 없음. 그래서 총 시간복잡도 O(NlogN) 으로 겨우 통과는 할 수 있음

 

역시 다른 사람 코드에 비해 엄청 느리고 메모리도 많이 쓴다고 통계가 나왔다

 

 

이 문제를 풀고 얻은 것

• python heapq 라이브러리 이해하고 써보기
• sliding window array 유형 하나는 풀어냄!!

메모

• ㅇ<-<...
• python set의 insert, search 시간복잡도는 둘 다 O(1) 이라고 한다
• leftidx, rightidx 라고 변수명을 지었어야 했는데.. min max가 여기저기 쓰여서 읽기 어려운 코드가 되었다
• 공식? 풀이를 봤는데 일단 Heap을 쓰는 접근이 첫 번째 풀이였다. 와 진짜 heap이 맞다고? 자신감 상승. 두 번째와 세 번째 풀이로는 OrderedDict와 deque를 쓰더라. 아 OrderedDict 라는 자료구조가 있었지 참..
• heap을 쓰는 풀이더라도 deleted set 뭐 이런 걸 관리할 필요가 없이, 어차피 heap에 index를 같이 저장하고 있으니까 min이나 max 값의 index를 얻어내서 그 Index까지는 프리패스로 minidx(leftidx 라고 이름지었어야 할 그것)를 증가시키면 된다. 그리고 min, max heap의 상단에 있는 원소가 leftidx보다 왼쪽 idx를 갖고 있다면 pop시키기.. 뭐야 완전 내 풀이랑 같은데 되게 깔끔하네
  • 공간복잡도는 O(N)
• deque를 쓰는 풀이는 시간복잡도가 O(N)인데, 핵심 아이디어는 나보다 먼저 들어왔던 숫자들은 내가 걔네보다 크다면 앞으로의 sliding window 에서도 걔네가 Max가 될 일은 없으니까 유지할 필요가 없다는 것이다 (내가 작을 때도 반대로 마찬가지). 그러니 나보다 먼저 들어왔으면서 나보다 큰 애들, 혹은 나보다 작더라도 나보다 나중에 들어온 애들만 갖고 있으면 된다 와우!
  그래서 heap처럼 tree구조를 유지할 필요 없이 컴팩트한 queue만 들고 있으면 된다는 점이 시간복잡도 차이를 만들어 낸다