nums라는 숫자 목록이 있고 오름차순으로 정렬되어 있다고 가정하고 두 개의 인접한 값 사이의 최대 차이가 가능한 한 최소가 되도록 목록에서 k 값을 삭제하고 마지막으로 차이를 찾아야 합니다.
따라서 입력이 nums =[15, 20, 30, 400, 1500] k =2와 같으면 출력은 10이 됩니다. 마치 [400, 1500]을 제거하여 20과 30의 차이를 구하는 것과 같습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- abs_diff :=nums의 모든 연속 요소의 차이 목록
- dp() 함수를 정의합니다. 이것은 i, j, cnt가 걸립니다
- cnt가 0과 같으면
- m :=0
- i~j 범위의 k에 대해 수행
- m :=m 및 abs_diff[k]의 최대값
- 반환 m
- dp(i + 1, j, cnt - 1) 및 dp(i, j - 1, cnt - 1)의 최소값 반환
- 기본 방법에서 다음을 수행합니다.
- dp(0, abs_diff의 크기 - 1, k)를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, nums, k): abs_diff = [nums[i] - nums[i - 1] for i in range(1, len(nums))] def dp(i, j, cnt): if cnt == 0: m = 0 for k in range(i, j + 1): m = max(m, abs_diff[k]) return m return min(dp(i + 1, j, cnt - 1), dp(i, j - 1, cnt - 1)) return dp(0, len(abs_diff) - 1, k) ob = Solution() nums = [15, 20, 30, 400, 1500] k = 2 print(ob.solve(nums, k))
입력
[15, 20, 30, 400, 1500], 2
출력
10