Python에서 K 증분 후 가장 긴 동등한 하위 목록을 찾는 프로그램

<시간/>

nums와 k라는 숫자 목록이 있다고 가정합니다. 이제 한 요소를 한 번 증가시킬 수 있는 작업을 고려하십시오. 최대 k 번 연산을 수행할 수 있다면 동일한 요소를 포함하는 가장 긴 하위 목록을 찾아야 합니다.

따라서 입력이 nums =[3, 5, 9, 6, 10, 7] k =6과 같으면 출력은 3이 됩니다. 하위 목록 [10, 10]을 얻기 위해 9를 한 번, 6을 네 번 증가시킬 수 있기 때문입니다. , 10].

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

숫자가 비어 있으면
- 0 반환
wMax :=nums와 같은 크기의 이중 종료 큐. 그리고 쌍을 삽입하십시오 (nums[0], 0)
나는 :=0, 포함 :=0
범위 1에서 숫자 크기까지의 j에 대해
- wMax는 비어 있지 않고 wMax[0, 1]
  - wMax의 왼쪽 요소 삭제
- pMax :=wMax[0, 0]
- wMax가 비어 있지 않고 wMax <=nums[j]의 마지막 항목의 첫 번째 요소인 동안 do
  - wMax에서 오른쪽 요소 삭제
- wMax의 끝에 (nums[j], j) 삽입
- pMax
  - inc =inc + (j - i) * (wMax[0, 0] - pMax)
- 그렇지 않으면
  - Inc :=Inc + pMax - nums[j]
- inc> k인 경우
  - inc :=inc - wMax[0, 0] - 숫자[i]
  - wMax가 비어 있지 않은 동안 wMax[0, 1] <=i, do
    - wMax의 왼쪽 요소 삭제
  - wMax[0, 0]
    - inc =inc - (nums[i] - wMax[0, 0]) * (j - i)
  - 나는 :=나는 + 1
숫자 반환 크기 - i

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

예

from collections import deque
class Solution:
   def solve(self, nums, k):
      if not nums:
         return 0
      wMax = deque([(nums[0], 0)], maxlen=len(nums))
      i = 0
      inc = 0
      for j in range(1, len(nums)):
         while wMax and wMax[0][1] < i:
            wMax.popleft()
         pMax = wMax[0][0]

         while wMax and wMax[-1][0] <= nums[j]:
            wMax.pop()
         wMax.append((nums[j], j))
         if pMax < wMax[0][0]:
            inc += (j - i) * (wMax[0][0] - pMax)
         else:
            inc += pMax - nums[j]
         if inc > k:
            inc -= wMax[0][0] - nums[i]
            while wMax and wMax[0][1] <= i:
               wMax.popleft()
            if wMax[0][0] < nums[i]:
               inc -= (nums[i] - wMax[0][0]) * (j - i)
            i += 1
      return len(nums) - i
ob = Solution()
nums = [3, 5, 9, 6, 10, 7]
k = 6
print(ob.solve(nums, k))

입력

[3, 5, 9, 6, 10, 7], 6