1.题目基本信息

1.1.题目描述

给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k 和 dist 。

一个数组的 代价 是数组中的 第一个 元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。

你需要将 nums 分割成 k 个 连续且互不相交 的子数组，满足 第二 个子数组与第 k 个子数组中第一个元素的下标距离 不超过 dist 。换句话说，如果你将 nums 分割成子数组 nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)] ，那么它需要满足 ik-1 - i1 <= dist 。

请你返回这些子数组的 最小 总代价。

1.2.题目地址

https://leetcode.cn/problems/divide-an-array-into-subarrays-with-minimum-cost-ii/description/

2.解题方法

2.1.解题思路

懒删除的对顶堆。题目转换：等价于求dist+1宽度的滑动窗口中最小的k-1个元素，所有合法滑动窗口中最小k-1个元素的和的最小值+nums[0]即为题解

2.2.解题步骤

第一步，构建维护变量。leftMaxHeap维护窗口中前k-1小的元素，rightMinHeap维护窗口中其余的大的元素。minSum维护leftMaxHeap中的最小和

第二步，滑动滑动窗口，更新懒删除堆，并更新最小代价

• 2.1.删除左端元素（可能不在堆中），并推入右端元素

• 2.2.维护leftMaxHeap堆的size为k-1

• 2.3.获取当前k-1尺寸的堆中元素的和

3.解题代码

python代码

# ==> 模板：懒删除小根堆
from collections import defaultdict
from heapq import heappush, heappop, heappushpop
class LazyMinHeap:
    def __init__(self):
        # 第一步，构建维护变量。heap维护最小堆；size维护最小堆中元素的个数；sum维护堆中所有元素的和；cnts维护堆中各个有效元素的频数；delayDelete维护待删除的各个元素的个数；
        self.heap = []
        self.size = 0
        self.sum = 0
        self.cnts = defaultdict(int)
        self.delayDelete = defaultdict(int)
    
    # 修剪堆顶部待删除的元素
    def prune(self):
        while self.heap:
            topVal = self.heap[0]
            if self.delayDelete[topVal] > 0:
                heappop(self.heap)
                self.delayDelete[topVal] -= 1
            else:
                break
    
    # 懒删除堆中的元素；这里必须保证val在堆中
    def delete(self, val:int):
        if self.cnts[val] > 0:
            self.cnts[val] -= 1
            self.delayDelete[val] += 1
            self.size -= 1
            self.sum -= val
            return True
        return False

    # 判断堆是否为空
    def empty(self):
        self.prune()
        return len(self.heap) == 0

    # 获取顶部元素
    def top(self):
        if self.empty():
            return
        return self.heap[0]

    # 堆中添加元素
    def push(self, val:int):
        if self.delayDelete[val] > 0:
            self.delayDelete[val] -= 1
        else:
            heappush(self.heap, val)
        self.cnts[val] += 1
        self.sum += val
        self.size += 1
    
    # 堆顶弹出元素
    def pop(self):
        if self.empty():
            return
        val = heappop(self.heap)
        self.cnts[val] -= 1
        self.size -= 1
        self.sum -= val
        return val
    
    def __str__(self):
        return f"size={self.size}\nsum={self.sum}\ndelayDelete={self.delayDelete}\ncnts={self.cnts}\nheap={self.heap}\n"



class Solution:
    def minimumCost(self, nums: List[int], k: int, dist: int) -> int:
        # 思路1：懒删除的对顶堆。题目转换：等价于求dist+1宽度的滑动窗口中最小的k-1个元素，所有合法滑动窗口中最小k-1个元素的和的最小值+nums[0]即为题解
        n = len(nums)
        width = dist + 1
        # 第一步，构建维护变量。leftMaxHeap维护窗口中前k-1小的元素，rightMinHeap维护窗口中其余的大的元素。minSum维护leftMaxHeap中的最小和
        leftMaxHeap = LazyMinHeap()
        rightMinHeap = LazyMinHeap()
        for i in range(1, width + 1):
            leftMaxHeap.push(-nums[i])
        for _ in range(width - (k - 1)):
            rightMinHeap.push(-leftMaxHeap.pop())
        minSum = -leftMaxHeap.sum
        # print(lazyHeap)
        # 第二步，滑动滑动窗口，更新懒删除堆，并更新最小代价
        for i in range(width + 1, n):
            # 2.1.删除左端元素（可能不在堆中），并推入右端元素
            val = nums[i - width]
            if leftMaxHeap.cnts[-val] > 0:
                leftMaxHeap.delete(-val)
            else:
                rightMinHeap.delete(val)
            if nums[i] < -leftMaxHeap.top():
                leftMaxHeap.push(-nums[i])
            else:
                rightMinHeap.push(nums[i])
            # 2.2.维护leftMaxHeap堆的size为k-1
            while leftMaxHeap.size > k - 1:
                rightMinHeap.push(-leftMaxHeap.pop())
            while leftMaxHeap.size < k - 1:
                leftMaxHeap.push(-rightMinHeap.pop())
            # 2.3.获取当前k-1尺寸的堆中元素的和
            minSum = min(minSum, -leftMaxHeap.sum)
            # print(i, lazyHeap)
        return minSum + nums[0]

4.执行结果