Algorithm // 최댓값과 최솟값을 추적 가능한 더블큐

서론

• 해당 글은 SortedList 가 아닌 방식으로 최소값과 최댓값을 트래킹하는 자료구조를 다릅니다.

class DoubleQueue:
    def __init__(self, nums: List[int]):
        self.arr = nums
        self.maxima = deque()
        self.minima = deque()
        self.size = 0

    def append(self, index: int) -> None:
        while self.maxima and self.arr[self.maxima[-1]] <= self.arr[index]:
            self.maxima.pop()
        self.maxima.append(index)

        while self.minima and self.arr[self.minima[-1]] >= self.arr[index]:
            self.minima.pop()
        self.minima.append(index)

        self.size += 1

    def minimum(self):
        if self.size == 0:
            return None
        return self.arr[self.minima[0]]

    def maximum(self):
        if self.size == 0:
            return None
        return self.arr[self.maxima[0]]

    def pop(self, index: int) -> bool:
        if self.size == 0:
            return False

        if self.maxima and self.maxima[0] == index:
            self.maxima.popleft()

        if self.minima and self.minima[0] == index:
            self.minima.popleft()

        self.size -= 1
        return True

설명

• 해당 알고리즘의 기본적인 원리는 두개의 모노토닉 큐를 이용해 가능한 최대, 최소값의 인덱스를 저장해 O(1) 의 속도로 주어진 배열에서 최소값과 최대값을 찾고 그 사이즈또한 리턴할수 있습니다.

• 여기서 중요한점은 값으로 인덱스를 저장해 데이터를 pop 할 때에 상태를 O(1) 로 관리한다는점입니다.