题目描述
力扣嘉年华为了确保更舒适的游览环境条件,在会场的各处设置了湿度调节装置,这些调节装置受控于总控室中的一台控制器。
控制器中已经预设了一些调节指令,整数数组 operate[i]
表示第 i
条指令增加空气湿度的大小。现在你可以将任意数量的指令修改为降低湿度(变化的数值不变),以确保湿度尽可能的适宜:
- 控制器会选择 一段连续的指令,从而进行湿度调节的操作;
- 这段指令最终对湿度影响的绝对值,即为当前操作的「不适宜度」
- 在控制器所有可能的操作中,最大 的「不适宜度」即为「整体不适宜度」
请返回在所有修改指令的方案中,可以得到的 最小「整体不适宜度」。
样例
输入:operate = [5,3,7]
输出:8
解释:对于方案 2 的 [5,3,-7]
操作指令 [5],[3],[-7] 的「不适宜度」分别为 5,3,7
操作指令 [5,3],[3,-7] 的「不适宜度」分别为 8,4
操作指令 [5,3,-7] 的「不适宜度」为 1,
因此对于方案 [5,3,-7]的「整体不适宜度」为 8,其余方案的「整体不适宜度」均不小于 8,如下表所示:
输入:operate = [20,10]
输出:20
限制
1 <= operate.length <= 1000
1 <= operate[i] <= 1000
算法
(动态规划) $O(nm)$
- 此题可以等价转为如下问题:在数轴上给定初始点 $0$,每次可以在上一次结束位置的基础上,正向或者负向移动 $d$ 的距离,到达新的位置,求最终可覆盖所有位置的线段长度最短是多少。
- 设状态 $f(i, j)$ 表示考虑了前 $i$ 次移动,且第 $i$ 次移动的结束位置到区间左边界的距离为 $j$ 时,到右边界的最短距离。$i$ 的有效下标从 $1$ 开始,$j$ 的范围是 $[0, 2d_{max}]$。可以证明,最终的最短线段长度不超过两倍最大的 $d$ 值。
- 初始时,$f(0, 0) = 0$,其余为正无穷。
- 转移时,假设已经求出了 $f(i, j)$,考虑第 $i + 1$ 个距离 $d$:
- 如果往负向移动,则更新 $f(i + 1, \max(0, j - d)) = \max(f(i + 1, \max(0, j - d)), f(i, j) + d)$。
- 如果往正向移动,则更新 $f(i + 1, j + d) = \max(f(i + 1, j + d), \max(0, f(i, j) - d))$。
- 最终答案为 $\min(j + f(n, j))$。
时间复杂度
- 状态数为 $O(nm)$,转移时间为常数,故时间复杂度为 $O(nm)$。
空间复杂度
- 需要 $O(nm)$ 的额外空间存储状态。
C++ 代码
const int N = 1001, M = 2100;
const int INF = 1000000000;
class Solution {
private:
int f[N][M];
public:
int unSuitability(vector<int>& operate) {
const int n = operate.size();
for (int i = 0; i <= n; i++)
for (int j = 0; j < M; j++)
f[i][j] = INF;
f[0][0] = 0;
for (int i = 0; i < n; i++) {
int d = operate[i];
for (int j = 0; j < M; j++) {
f[i + 1][max(0, j - d)] = min(f[i + 1][max(0, j - d)], f[i][j] + d);
if (j + d < M)
f[i + 1][j + d] = min(f[i + 1][j + d], max(0, f[i][j] - d));
}
}
int ans = INF;
for (int j = 0; j < M; j++)
ans = min(ans, j + f[n][j]);
return ans;
}
};