工作计划的最低难度

标签: 数组 动态规划

难度: Hard

你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。

你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。

给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。

返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。

示例 1：

输入：jobDifficulty = [6,5,4,3,2,1], d = 2
输出：7
解释：第一天，您可以完成前 5 项工作，总难度 = 6.
第二天，您可以完成最后一项工作，总难度 = 1.
计划表的难度 = 6 + 1 = 7

示例 2：

输入：jobDifficulty = [9,9,9], d = 4
输出：-1
解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。

示例 3：

输入：jobDifficulty = [1,1,1], d = 3
输出：3
解释：工作计划为每天一项工作，总难度为 3 。

示例 4：

输入：jobDifficulty = [7,1,7,1,7,1], d = 3
输出：15

示例 5：

输入：jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
输出：843

提示：

  • 1 <= jobDifficulty.length <= 300
  • 0 <= jobDifficulty[i] <= 1000
  • 1 <= d <= 10

Submission

运行时间: 37 ms

内存: 16.1 MB

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        f = list(accumulate(jobDifficulty, max))
        for i in range(1, d):
            stk = []
            pre = f[i-1]
            for j in range(i, n):
                mn = pre
                pre = f[j]
                while stk and jobDifficulty[stk[-1][0]]<jobDifficulty[j]:
                    mn = min(mn, stk.pop()[1])
                f[j] = mn+jobDifficulty[j]
                if stk:
                    f[j] = min(f[j], f[stk[-1][0]])
                stk.append((j, mn))
        return f[-1] if n>=d else -1

Explain

这个题解使用了动态规划和单调栈的结合来解决问题。初始化一个动态规划数组f，其中f[i]代表完成前i+1项工作的最小难度。使用一个单调栈来优化查找过程，栈中存储的是元组(j, mn)，其中j是索引，mn是到j为止的最小值。遍历工作计划，利用栈来维持一种单调递增的状态，从而快速计算出完成指定天数工作的最小难度。在迭代中，每次尝试更新f数组表示分割后的最优解。如果栈中的工作难度小于当前工作难度，将其弹出。每一天都计算完成工作的最大难度，更新f数组。通过单调栈来快速得到分割点以前的最优难度。

时间复杂度: O(d * n)

空间复杂度: O(n)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        # 使用accumulate计算前缀最大难度
        f = list(accumulate(jobDifficulty, max))
        # 外层循环天数，内层循环工作难度数组
        for i in range(1, d):
            stk = []  # 单调栈
            pre = f[i-1]
            for j in range(i, n):
                mn = pre
                pre = f[j]
                # 维持栈的单调性，确保可以快速计算最小难度
                while stk and jobDifficulty[stk[-1][0]] < jobDifficulty[j]:
                    mn = min(mn, stk.pop()[1])
                f[j] = mn + jobDifficulty[j]
                # 检查并更新当前的最优值
                if stk:
                    f[j] = min(f[j], f[stk[-1][0]])
                stk.append((j, mn))
        # 如果任务数小于天数，返回-1，否则返回最小难度总和
        return f[-1] if n >= d else -1

Explore

在这个题解中，动态规划用于确定分割工作计划以最小化总难度。动态规划数组f记录了完成前i+1项工作的最小难度。单调栈则用于优化动态规划的过程中对最小值的快速查找和更新。在更新f数组时，单调栈帮助快速确定之前的最小难度值。通过维护栈的单调递增性质，可以确保在寻找最小难度时不需要回溯整个数组，从而提高效率。这种结合方式允许动态规划在每一步都利用单调栈提供的最优历史数据，快速更新状态。

在题解的动态规划过程中，f数组的每个元素f[i]代表的是完成前i+1项工作，且恰好分割成当前考虑的天数时所能达到的最小难度总和。具体来说，f[i]反映了将前i+1项工作分配到已考虑的天数中，每天工作的难度最大值的总和的最小可能值。

在题解中，单调栈用来在迭代过程中维持一个工作难度的递减顺序。当遍历到新的工作难度时，如果当前工作难度大于栈顶元素的难度，之前的低难度工作将被弹出栈，这样可以确保每天考虑的工作难度是最大可能的。然后，栈中存储的是一个元组（工作索引，到该索引为止的最小难度），这样可以在计算分割点以前的最优难度时提供快速访问。

单调栈在题解中通过在每个迭代中检查并可能弹出栈顶元素来维持其单调递减性。具体来说，当遇到一个新的工作难度大于栈顶工作难度时，栈顶元素会被弹出。这样做的目的是确保栈中的每个元素都代表了在此之前遇到的最大难度，从而在计算分割工作的最小总难度时，可以快速获取到前面工作的最小难度。维持单调性能够减少每次更新f数组时的计算量，使得算法更加高效。