努力

2哥 : 3妹，脸上的豆豆好了没呢。
3妹：好啦，现在已经没啦
2哥 : 跟你说很快就会消下去的，还不信~ 既然你的容颜和心情都如此美丽，那我们就再做一道关于美丽的题吧。
3妹：切，2哥就会取笑我，伤心时让我做题，开心时也让我做题！

题目：

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和一个整数 k 。

你可以执行下述 递增 运算 任意 次（可以是 0 次）：

从范围 [0, n - 1] 中选择一个下标 i ，并将 nums[i] 的值加 1 。
如果数组中任何长度 大于或等于 3 的子数组，其 最大 元素都大于或等于 k ，则认为数组是一个 美丽数组 。

以整数形式返回使数组变为 美丽数组 需要执行的 最小 递增运算数。

子数组是数组中的一个连续 非空 元素序列。

示例 1：

输入：nums = [2,3,0,0,2], k = 4
输出：3
解释：可以执行下述递增运算，使 nums 变为美丽数组：
选择下标 i = 1 ，并且将 nums[1] 的值加 1 -> [2,4,0,0,2] 。
选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,3] 。
选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,4] 。
长度大于或等于 3 的子数组为 [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4] 。
在所有子数组中，最大元素都等于 k = 4 ，所以 nums 现在是美丽数组。
可以证明无法用少于 3 次递增运算使 nums 变为美丽数组。
因此，答案为 3 。
示例 2：

输入：nums = [0,1,3,3], k = 5
输出：2
解释：可以执行下述递增运算，使 nums 变为美丽数组：
选择下标 i = 2 ，并且将 nums[2] 的值加 1 -> [0,1,4,3] 。
选择下标 i = 2 ，并且将 nums[2] 的值加 1 -> [0,1,5,3] 。
长度大于或等于 3 的子数组为 [0,1,5]、[1,5,3]、[0,1,5,3] 。
在所有子数组中，最大元素都等于 k = 5 ，所以 nums 现在是美丽数组。
可以证明无法用少于 2 次递增运算使 nums 变为美丽数组。
因此，答案为 2 。
示例 3：

输入：nums = [1,1,2], k = 1
输出：0
解释：在这个示例中，只有一个长度大于或等于 3 的子数组 [1,1,2] 。
其最大元素 2 已经大于 k = 1 ，所以无需执行任何增量运算。
因此，答案为 0 。

提示：

3 <= n == nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= k <= 10^9

思路：

思考

记忆化搜索
把大于 k 的元素视作 k。

由于大于 3 的子数组必然包含等于 3 的子数组，问题转换成：每个长为 3 的子数组都需要包含至少一个 k。
详解如代码中注释：

java代码：

class Solution {
    public int minChanges(String s) {
        // 1、压缩数据，列表每个元素都是连续0或1子串的长度
        List<Integer> cntList = new ArrayList<>();
        char preC = s.charAt(0);
        int cnt = 0;
        for (char c : s.toCharArray()) {
            // 和上一个字符比较，判断是否连续相同
            if (c == preC) {
                cnt++;
            } else {
                // 记录子串长度
                cntList.add(cnt);
                cnt = 1;
            }
            preC = c;
        }
        cntList.add(cnt);

        int minChangeCnt = 0;
        // 2、对压缩列表相邻元素（子串长度）奇偶判断
        for (int i = 0; i < cntList.size(); i++) {
            cnt = cntList.get(i);
            if (cnt % 2 == 0) {
                // 跳过偶数
                continue;
            }
            // 奇数，预取下一个
            int nextCnt = cntList.get(i + 1);
            if (nextCnt % 2 == 1) {
                // 下一个奇数，调整1个。例：{1,3}=>{2,2}
                minChangeCnt++;
                // 已调整，跳过下一个
                i++;
            } else {
                // 下一个是偶数，当前子串调整1个，下一个子串减1
                minChangeCnt++;
                cntList.set(i + 1, nextCnt - 1);
            }
        }
        return minChangeCnt;
    }
}