nums라는 숫자 목록과 값 k가 있다고 가정합니다. 먼저 크기 k의 하위 목록을 제거한 다음 최소값(최대값 - 최소값)을 찾습니다.
따라서 입력이 nums =[2, 3, 10, 9, 8, 4] k =3과 같으면 출력은 2가 됩니다. [10, 9, 8]을 제거하면 [2, 3, 4] 및 4 - 2 =2
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
N :=숫자 크기
-
lmin 및 lmax에 숫자 복사
-
또한 rmin 및 rmax에 숫자를 복사합니다.
-
범위 1에서 N - 1까지의 i에 대해 수행
-
lmin[i] :=lmin[i] 및 lmin[i - 1]의 최소값
-
lmax[i] :=lmax[i] 및 lmax[i - 1]의 최대값
-
-
범위 N - 2에서 0의 i에 대해 1 감소, 수행
-
rmin[i] :=rmin[i] 및 rmin[i + 1]의 최소값
-
rmax[i] :=rmax[i] 및 rmax[i + 1]의 최대값
-
-
ans :=(rmax[k] - rmin[k])의 최소값, (lmax[k의 보수] - lmin[k의 보수])
-
0 ~ N - k - 2 범위의 i에 대해 수행
-
cand :=(lmax[i] 및 rmax[i + k + 1]의 최대값) - (lmin[i] 및 rmin[i + k + 1]의 최소값)
-
ans :=ans와 cand의 최소값
-
-
반환
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(nums, k): N = len(nums) lmin, lmax = nums[:], nums[:] rmin, rmax = nums[:], nums[:] for i in range(1, N): lmin[i] = min(lmin[i], lmin[i - 1]) lmax[i] = max(lmax[i], lmax[i - 1]) for i in range(N - 2, -1, -1): rmin[i] = min(rmin[i], rmin[i + 1]) rmax[i] = max(rmax[i], rmax[i + 1]) ans = min(rmax[k] - rmin[k], lmax[~k] - lmin[~k]) for i in range(N - k - 1): cand = max(lmax[i], rmax[i + k + 1]) - min(lmin[i], rmin[i + k + 1]) ans = min(ans, cand) return ans nums = [2, 3, 10, 9, 8, 4] k = 3 print(solve(nums, k))
입력
[2, 3, 10, 9, 8, 4], 3
출력
2