工作计划的最低难度
难度:
标签:
题目描述
你需要制定一份 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 <= 3000 <= jobDifficulty[i] <= 10001 <= d <= 10
代码结果
运行时间: 37 ms, 内存: 16.1 MB
import java.util.Arrays;
import java.util.stream.IntStream;
/**
* 思路：使用动态规划（DP）来解决这个问题。
* dp[i][j] 表示前 i 个工作在 j 天内完成的最小难度。
* 对于每一天的最后一个任务 k，可以递归计算其前一天的最小难度和当天的最大难度。
* 使用 Java Stream API 简化代码。
*/
public class JobScheduleStream {
public int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
if (n < d) return -1;
int[][] dp = new int[d + 1][n + 1];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[0][0] = 0;
IntStream.rangeClosed(1, d).forEach(i -> {
IntStream.rangeClosed(i, n).forEach(j -> {
int[] maxDiff = {0};
IntStream.iterate(j, k -> k - 1).limit(j - i + 1).forEach(k -> {
maxDiff[0] = Math.max(maxDiff[0], jobDifficulty[k - 1]);
if (dp[i - 1][k - 1] != Integer.MAX_VALUE) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k - 1] + maxDiff[0]);
}
});
});
});
return dp[d][n];
}
}解释
方法:
这个题解使用了动态规划和单调栈的结合来解决问题。初始化一个动态规划数组f，其中f[i]代表完成前i+1项工作的最小难度。使用一个单调栈来优化查找过程，栈中存储的是元组(j, mn)，其中j是索引，mn是到j为止的最小值。遍历工作计划，利用栈来维持一种单调递增的状态，从而快速计算出完成指定天数工作的最小难度。在迭代中，每次尝试更新f数组表示分割后的最优解。如果栈中的工作难度小于当前工作难度，将其弹出。每一天都计算完成工作的最大难度，更新f数组。通过单调栈来快速得到分割点以前的最优难度。
时间复杂度:
O(d * n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中提到使用动态规划和单调栈的结合，能否具体解释这两种数据结构是如何结合在一起的？
▷🦆
在题解的动态规划过程中，f数组的每个元素代表的具体含义是什么？
▷🦆
题解中提到每天都计算完成工作的最大难度，这是如何通过单调栈实现的？
▷🦆
单调栈在题解中是如何维持其单调性的，以及为什么要维持这种单调性？
▷