题目描述
给你一个下标从 0 开始长度为 n
的整数数组 nums
。
从 0
到 n - 1
的数字被分为编号从 1
到 3
的三个组,数字 i
属于组 nums[i]
。注意,有的组可能是 空的。
你可以执行以下操作任意次:
- 选择数字
x
并改变它的组。更正式的,你可以将nums[x]
改为数字1
到3
中的任意一个。
你将按照以下过程构建一个新的数组 res
:
- 将每个组中的数字分别排序。
- 将组
1
,2
和3
中的元素 依次 连接以得到res
。
如果得到的 res
是 非递减顺序的,那么我们称数组 nums
是 美丽数组。
请你返回将 nums
变为 美丽数组 需要的最少步数。
样例
输入:nums = [2,1,3,2,1]
输出:3
解释:以下三步操作是最优方案:
1. 将 nums[0] 变为 1。
2. 将 nums[2] 变为 1。
3. 将 nums[3] 变为 1。
执行以上操作后,将每组中的数字排序,组 1 为 [0,1,2,3,4],组 2 和组 3 都为空。
所以 res 等于 [0,1,2,3,4],它是非递减顺序的。
三步操作是最少需要的步数。
输入:nums = [1,3,2,1,3,3]
输出:2
解释:以下两步操作是最优方案:
1. 将 nums[1] 变为 1。
2. 将 nums[2] 变为 1。
执行以上操作后,将每组中的数字排序,组 1 为 [0,1,2,3],组 2 为空,组 3 为 [4,5]。
所以 res 等于 [0,1,2,3,4,5],它是非递减顺序的。
两步操作是最少需要的步数。
输入:nums = [2,2,2,2,3,3]
输出:0
解释:不需要执行任何操作。
组 1 为空,组 2 为 [0,1,2,3],组 3 为 [4,5]。所以 res 等于 [0,1,2,3,4,5],它是非递减顺序的。
限制
1 <= nums.length <= 100
1 <= nums[i] <= 3
算法
(动态规划) $O(n)$
- 翻译一下题目,相当于求最小的修改次数,使得数组变为
11...22...33
单调不降的顺序。 - 设状态 $f(i, j)$ 表示访问了前 $i$ 个位置,最终以数字 $j$ 结尾的最小修改次数。其中 $i$ 的范围为 $[0, n - 1]$,$j$ 为 $1$,$2$ 或 $3$。
- 初始时,如果 $nums(0) == 1$,则 $f(0, 1) = 0, f(0, 2) = f(0, 3) = 1$,其余情况同理。
- 转移时,对于 $f(i, 1)$,转移 $f(i, 1) = f(i - 1, 1) + (nums(i) \neq 1)$;对于 $f(i, 2)$,可以转移 $\min(f(i - 1, 1), f(i - 1, 2)) + (nums(i) \ neq 2)$;同理对于 $f(i, 3)$,可以转移 $\min(f(i - 1, 1), f(i - 1, 2), f(i - 1, 3)) + (nums(i) \neq 3)$。
- 最终答案为 $\min(f(n - 1, 1), f(n - 1, 2), f(n - 1, 3))$。
- 可以使用滚动数组优化掉第一维的状态表示。
时间复杂度
- 状态数为 $O(n)$,转移时间为常数,故时间复杂度为 $O(n)$。
空间复杂度
- 使用滚动数组,仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minimumOperations(vector<int>& nums) {
const int n = nums.size();
int f1 = 1, f2 = 1, f3 = 1;
if (nums[0] == 1) f1 = 0;
else if (nums[0] == 2) f2 = 0;
else f3 = 0;
for (int i = 1; i < n; i++) {
int t1 = f1 + (nums[i] != 1);
int t2 = min(f1, f2) + (nums[i] != 2);
int t3 = min(f1, min(f2, f3)) + (nums[i] != 3);
f1 = t1; f2 = t2; f3 = t3;
}
return min(f1, min(f2, f3));
}
};