최대 차이가 K인 파티션 배열

정수 배열nums과 정수k가 제공됩니다. nums의 각 요소가 하위 시퀀스 중 정확히 하나에 나타나도록 nums를 하나 이상의 하위 시퀀스로 분할할 수 있습니다.

각 하위 시퀀스의 최대값과 최소값의 차이가 최대k가 되도록 필요한 최소 하위 시퀀스 수를 반환합니다.

하위 시퀀스는 나머지 요소의 순서를 변경하지 않고 일부 요소를 삭제하거나 전혀 삭제하지 않음으로써 다른 시퀀스에서 파생될 수 있는 시퀀스입니다.

예 1:

입력: 숫자 = [3,6,1,2,5], k = 2
출력: 2
설명:
숫자를 두 개의 하위 시퀀스 [3,1,2]와 [6,5]로 분할할 수 있습니다.
첫 번째 하위 시퀀스의 최대값과 최소값의 차이는 3 - 1 = 2입니다.
두 번째 하위 시퀀스에서 최대값과 최소값의 차이는 6 - 5 = 1입니다.
두 개의 하위 시퀀스가 ​​생성되었으므로 2를 반환합니다. 2가 필요한 하위 시퀀스의 최소 개수임을 알 수 있습니다.

예 2:

입력: 숫자 = [1,2,3], k = 1
출력: 2
설명:
숫자를 두 개의 하위 시퀀스 [1,2] 및 [3]으로 분할할 수 있습니다.
첫 번째 하위 시퀀스의 최대값과 최소값의 차이는 2 - 1 = 1입니다.
두 번째 하위 시퀀스에서 최대값과 최소값의 차이는 3 - 3 = 0입니다.
두 개의 하위 시퀀스가 ​​생성되었으므로 2를 반환합니다. 또 다른 최적의 솔루션은 숫자를 두 개의 하위 시퀀스 [1]과 [2,3]으로 분할하는 것입니다.

예 3:

입력: 숫자 = [2,2,4,5], k = 0
출력: 3
설명:
숫자를 세 개의 하위 시퀀스 [2,2], [4] 및 [5]로 분할할 수 있습니다.
첫 번째 하위 시퀀스에서 최대값과 최소값의 차이는 2 - 2 = 0입니다.
두 번째 하위 시퀀스에서 최대값과 최소값의 차이는 4 - 4 = 0입니다.
세 번째 하위 시퀀스에서 최대값과 최소값의 차이는 5 - 5 = 0입니다.
3개의 하위 시퀀스가 ​​생성되었으므로 3을 반환합니다. 3이 필요한 하위 시퀀스의 최소 개수임을 알 수 있습니다.

제약:

1 <= nums.length <= 105

0 <= nums[i] <= 105

0 <= k <= 105

해결책:

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if k == 0:
            return len(set(nums))
        nums.sort()
        subs = [[float('inf'), float('-inf')] for i in range(n)]
        res = 0
        for num in nums:
            for i in range(n):
                mn, mx = subs[i]
                nmn = min(mn, num)
                nmx = max(mx, num)
                if nmx - nmn <= k:
                    subs[i][0], subs[i][1] = nmn, nmx
                    res = max(res, i + 1)
                    break
        return res