题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个整数数组，和两个整数 k 和 dist，要将这个数组分为 k 个连续且互不相交的子数组，其中第二个子数组和最后一个的首个元素下标之差不超过 dist，求怎么分割使得所有子数组的代价最小（代价就是每个子数组的第一个元素值）

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class LazyHeap:
    def __init__(self):
        self.heap = []
        self.size = 0
        self.remove_cnt = defaultdict(int)
        self.sum = 0
    
    def push(self, num):
        self.apply_remove()
        heappush(self.heap, num)
        self.size += 1
        self.sum += num

    def pop(self) -> int:
        self.apply_remove()
        self.size -= 1
        self.sum -= self.heap[0]
        return heappop(self.heap)

    def pushpop(self, num) -> int:
        self.push(num)
        return self.pop()
    
    def top(self) -> int:
        self.apply_remove()
        return self.heap[0]
    
    def remove(self, num):
        self.remove_cnt[num] += 1
        self.size -= 1
        self.sum -= num

    def apply_remove(self):
        while self.heap and self.remove_cnt[self.heap[0]]:
            self.remove_cnt[self.heap[0]] -= 1
            heappop(self.heap)

class Solution:
    def minimumCost(self, nums: List[int], k: int, dist: int) -> int:
        # left 用来保存已有的 k-1 个最小的数用来建数组
        left = LazyHeap()
        right = LazyHeap()
        ans = inf
        n = len(nums)
        k -= 1
        for i in range(1, n):
            if left.size < k:
                left.push(-right.pushpop(nums[i]))
            else:
                right.push(-left.pushpop(-nums[i]))

            if i < dist+1:
                continue

            ans = min(ans, -left.sum)

            to_del = i-dist
            if nums[to_del] > -left.top():
                right.remove(nums[to_del])
            else:
                left.remove(-nums[to_del])

        return nums[0] + ans