Python에서 min과 max의 차이가 k보다 작은 가장 긴 하위 목록의 길이를 찾는 프로그램

<시간/>

nums라는 숫자 목록과 또 다른 값 k가 있다고 가정하면 가장 큰 요소와 가장 작은 요소 간의 절대 차이가 ≤ k인 가장 긴 하위 목록의 길이를 찾아야 합니다.

따라서 입력이 nums =[2, 4, 6, 10] k =4와 같은 경우 출력은 3이 됩니다. 여기서 [2, 4, 6]을 선택할 수 있으므로 절대 차이는 4입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

최대 2개의 이중 종료 대기열 만들기
i :=0, res :=1
A의 각 인덱스 j와 값에 대해 다음을 수행합니다.
- maxd가 0이 아니고 maxd의> 마지막 요소인 동안 do
  - maxd에서 마지막 요소 삭제
- 마인드가 0이 아니고 <마인드의 마지막 요소인 동안 do
  - 마지막 요소 삭제
- maxd 끝에 삽입
- 끝에 삽입
- maxd[0] - 마음[0]> 제한, 수행
  - maxd[0]이 A[i]와 같으면
    - maxd의 왼쪽에서 항목 삭제
  - 마음[0]이 A[i]와 같으면
    - 기억에 남는 항목 삭제
  - 나는 :=나는 + 1
- res :=최대 res 및 (j - i + 1)
반환 결과

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

from collections import deque, defaultdict
class Solution:
   def solve(self, A, limit):
      maxd = deque()
      mind = deque()
      i = 0
      res = 1
      for j, a in enumerate(A):
         while maxd and a > maxd[-1]:
            maxd.pop()
         while mind and a < mind[-1]:
            mind.pop()
         maxd.append(a)
         mind.append(a)
         while maxd[0] - mind[0] > limit:
            if maxd[0] == A[i]:
               maxd.popleft()
            if mind[0] == A[i]:
               mind.popleft()
            i += 1
            res = max(res, j - i + 1)
      return res
ob = Solution()
nums = [2, 4, 6, 10]
k = 4
print(ob.solve(nums, k))

입력

[2, 4, 6, 10], 4