6144. 将数组排序的最少替换次数

给你一个下表从 0 开始的整数数组 nums 。每次操作中，你可以将数组中任何一个元素替换为 任意两个 和为该元素的数字。

• 比方说，nums = [5,6,7] 。一次操作中，我们可以将 nums[1] 替换成 2 和 4 ，将 nums 转变成 [5,2,4,7] 。

请你执行上述操作，将数组变成元素按 非递减 顺序排列的数组，并返回所需的最少操作次数。

示例 1：

输入：nums = [3,9,3]
输出：2
解释：以下是将数组变成非递减顺序的步骤：
- [3,9,3] ，将9 变成 3 和 6 ，得到数组 [3,3,6,3] 
- [3,3,6,3] ，将 6 变成 3 和 3 ，得到数组 [3,3,3,3,3] 
总共需要 2 步将数组变成非递减有序，所以我们返回 2 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：数组已经是非递减顺序，所以我们返回 0 。

提示：

• 1 <= nums.length <= 1e5
• 1 <= nums[i] <= 1e9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

失败，被自己乱写一个case卡死 [2,7,3]，第二个7的替换策略想不通

方法：贪心

1. 从后向前找

2. 如果比后面的大，就按后面的数字平分，看看能分几份，如果整除，后续数字不变，分成 part-1份（西瓜切两半只要一刀）

3. 如果不能整除，则尽可能地均分，增大开头的数字，由于没整除，多分出一份 next+1 份，尽可能平均让开头数字变大

class Solution {
    public long minimumReplacement(int[] nums) {
        int n = nums.length;
        long ans = 0L;
        int next = nums[n-1];
        for(int i = n-2; i >= 0; i--){
            if(nums[i]>next){
                int part = nums[i]/next;
                if(nums[i]%next==0) {
                    ans += part-1;
                }else{
                    ans += part;
                    next = nums[i]/(part+1);
                }
            }else next = nums[i];
        }
        return ans;
    }
}

6138. 最长理想子序列

给你一个由小写字母组成的字符串 s ，和一个整数 k 。如果满足下述条件，则可以将字符串 t 视作是 理想字符串 ：

• t 是字符串 s 的一个子序列。
• t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k 。

返回 最长 理想字符串的长度。

字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。

注意：字母表顺序不会循环。例如，'a' 和 'z' 在字母表中位次的绝对差值是 25 ，而不是 1 。

示例 1：

输入：s = "acfgbd", k = 2
输出：4
解释：最长理想字符串是 "acbd" 。该字符串长度为 4 ，所以返回 4 。
注意 "acfgbd" 不是理想字符串，因为 'c' 和 'f' 的字母表位次差值为 3 。

示例 2：

输入：s = "abcd", k = 3
输出：4
解释：最长理想字符串是 "abcd" ，该字符串长度为 4 ，所以返回 4 。

提示：

• 1 <= s.length <= 105
• 0 <= k <= 25
• s 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-ideal-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，这题是中等，直接秒了

 方法：动态规划

前一个范围 max(index-k) 到 min(index+k 25) 都可以延长一个到当前字母，选取里面最长的一个和自己相连，注意自己长度是1需要额外增加一个。

class Solution {
        public int longestIdealString(String s, int k) {
            int[] dp = new int[26];
            int n = s.length();
             int ans = 0;
            for(int i = 0; i < n; i++){
                int v =0 ;
                int index = s.charAt(i)-'a';
                for(int start = Math.max(index-k,0); start<=Math.min(index+k,25);start++){
                    v=Math.max(dp[start],v);
                }
                dp[index] = v+1;
                ans = Math.max(v+1,ans);
            }
           
            return ans;
        }
    }