단조성 불변식 점검표

단조 구조 불변식 점검표

단조 스택과 단조 큐는 원소를 한 번 넣고 한 번 빼면서 후보 집합의 정렬된 의미를 계속 유지합니다.

꺼내는 기준

새 값이 후보를 무효화

다음 큰 수에서는 현재 값보다 작은 이전 원소를 빼며 답을 확정합니다.

인덱스 보존

값과 위치를 같이 저장

창 크기, 거리, 기간을 계산하려면 값만이 아니라 원래 인덱스가 필요합니다.

창 만료

범위를 벗어난 후보 제거

슬라이딩 윈도우에서는 왼쪽 경계를 지난 원소를 먼저 빼야 최댓값이 유효합니다.

제출 전 남길 증거

NGE 스택 top보다 큰 값을 만나면 top들의 답이 현재 값으로 정해집니다.
윈도우 최대 덱 앞은 현재 창에서 가장 큰 값의 인덱스를 유지합니다.
가격 기간 가격이 떨어지는 순간 이전 후보들의 지속 시간이 확정됩니다.