解法

思路和算法

为了使选择的 $k$ 个孩子的幸福值之和最大，应遵循如下贪心策略：按照幸福值递减的顺序选择幸福值最大的 $k$ 个孩子。理由如下。

1. 如果将幸福值最大的 $k$ 个孩子中的任意一个孩子更换成一个幸福值较小的孩子，则更换之后的孩子的幸福值一定不变或减少，不可能增加，因此幸福值之和不可能更大。

2. 当选择幸福值最大的 $k$ 个孩子时，如果这 $k$ 个孩子的初始幸福值都不小于 $k - 1$ 则幸福值之和的总减少量等于 $\dfrac{k(k + 1)}{2}$，如果这 $k$ 个孩子中存在孩子的初始幸福值小于 $k - 1$ 则幸福值之和的总减少量小于 $\dfrac{k(k + 1)}{2}$。假设两个孩子的幸福值分别为 $x$ 和 $y$，其中 $x > y$，则先选择 $x$ 后选择 $y$ 的幸福值之和等于 $x + \max(y - 1, 0)$，先选择 $y$ 后选择 $x$ 的幸福值之和等于 $y + \max(x - 1, 0)$，由于 $x > y > 0$，因此 $\max(x - 1, 0) = x - 1$，$x + \max(y - 1, 0) \ge y + \max(x - 1, 0)$，即先选择 $x$ 后选择 $y$ 的方案更优。

根据贪心策略，计算选中的孩子的幸福值之和的最大值的方法如下。

1. 将数组 $\textit{happiness}$ 按升序排序。

2. 用 $n$ 表示数组 $\textit{happiness}$ 的长度，反向遍历排序后的数组 $\textit{happiness}$，对于每个 $1 \le i \le k$，需要选择幸福值为 $\textit{happiness}[n - i]$ 的孩子，该孩子被选择时的幸福值为 $\max(\textit{happiness}[n - i] - (i - 1), 0)$，计算选中的孩子的幸福值之和。

实现方面，反向遍历排序后的数组 $\textit{happiness}$ 时，当遇到 $\textit{happiness}[n - i] \le i - 1$ 时，其余孩子的幸福值一定都是 $0$，此时即可结束遍历。

遍历结束之后，即可得到选中的孩子的幸福值之和的最大值。

代码

###Java

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        long sum = 0;
        Arrays.sort(happiness);
        int n = happiness.length;
        for (int i = 1; i <= k && happiness[n - i] > i - 1; i++) {
            int curr = happiness[n - i] - (i - 1);
            sum += curr;
        }
        return sum;
    }
}

###C#

public class Solution {
    public long MaximumHappinessSum(int[] happiness, int k) {
        long sum = 0;
        Array.Sort(happiness);
        int n = happiness.Length;
        for (int i = 1; i <= k && happiness[n - i] > i - 1; i++) {
            int curr = happiness[n - i] - (i - 1);
            sum += curr;
        }
        return sum;
    }
}

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{happiness}$ 的长度。将数组 $\textit{happiness}$ 排序的时间是 $O(n \log n)$，排序后遍历数组 $\textit{happiness}$ 计算选中的孩子的幸福值之和的最大值的时间是 $O(n)$，因此时间复杂度是 $O(n \log n)$。

• 空间复杂度：$O(\log n)$，其中 $n$ 是数组 $\textit{happiness}$ 的长度。排序的递归调用栈空间是 $O(\log n)$。

解法

思路和算法

这道题要求在数组 $\textit{strs}$ 中删除尽可能少的下标处的字符，满足每个字符串剩余字符都按字典序排序。为了使删除的下标个数最少，应使保留的下标个数最多，因此问题等价于计算数组 $\textit{strs}$ 中的所有字符串的最长公共递增子序列的长度，这里的公共的含义是下标相同。

用 $n$ 表示数组 $\textit{strs}$ 的长度，用 $m$ 表示数组 $\textit{strs}$ 中每个字符串的长度。对于 $0 \le i < m$，需要分别计算以每个下标 $i$ 结尾的最长公共递增子序列的长度，得到所有字符串的最长公共递增子序列的长度。如果存在下标 $j$ 满足 $0 \le j < i$ 且下标 $j$ 和下标 $i$ 都保留，则应满足对于所有 $0 \le k < n$ 都有 $\textit{strs}[k][j] \le \textit{strs}[k][i]$，在每个字符串的下标 $j$ 的字符之后添加下标 $i$ 的字符即可得到新的公共递增子序列。因此可以使用动态规划计算以每个下标结尾的最长公共递增子序列的长度。

为方便表述，对于给定下标 $i$，如果下标 $j$ 满足 $0 \le j < i$ 且对于所有 $0 \le k < n$ 都有 $\textit{strs}[k][j] \le \textit{strs}[k][i]$，则称下标 $j$ 是下标 $i$ 的「前驱下标」。

创建长度为 $m$ 的数组 $\textit{dp}$，其中 $\textit{dp}[i]$ 为以下标 $i$ 结尾的最长公共递增子序列长度。由于以任意一个下标结尾的最长公共递增子序列长度都大于等于 $1$，因此将 $\textit{dp}$ 中的所有值初始化为 $1$。

当 $i = 0$ 时，每个字符串的以下标 $i$ 结尾的子序列都只有一个，长度为 $1$，因此动态规划的边界情况是 $\textit{dp}[0] = 1$。

当 $i > 0$ 时，对于下标 $i$ 的任意前驱下标 $j$，$\textit{dp}[i] \ge \textit{dp}[j] + 1$，为了使 $\textit{dp}[i]$ 最大化，应寻找符合要求的最大的 $\textit{dp}[j]$，此时 $\textit{dp}[i] = \max{\textit{dp}[j]} + 1$。因此动态规划的状态转移方程是：对于下标 $i$ 的所有前驱下标 $j$，$\textit{dp}[i] = \max {\textit{dp}[j]} + 1$。

由于每一项依赖于之前的项，因此应从小到大遍历每个 $i$ 并计算 $\textit{dp}[i]$。计算得到 $\textit{dp}$ 中的所有状态值之后，其中的最大值即为最长公共递增子序列的长度。

用 $\textit{maxRemain}$ 表示 $\textit{dp}$ 中的最大值，则最多保留的下标个数是 $\textit{maxRemain}$，最少删除的下标个数是 $m - \textit{maxRemain}$。

代码

class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length, m = strs[0].length();
        int[] dp = new int[m];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < i; j++) {
                boolean sorted = true;
                for (int k = 0; k < n && sorted; k++) {
                    if (strs[k].charAt(j) > strs[k].charAt(i)) {
                        sorted = false;
                    }
                }
                if (sorted) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxRemain = 0;
        for (int remain : dp) {
            maxRemain = Math.max(maxRemain, remain);
        }
        return m - maxRemain;
    }
}

public class Solution {
    public int MinDeletionSize(string[] strs) {
        int n = strs.Length, m = strs[0].Length;
        int[] dp = new int[m];
        Array.Fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < i; j++) {
                bool sorted = true;
                for (int k = 0; k < n && sorted; k++) {
                    if (strs[k][j] > strs[k][i]) {
                        sorted = false;
                    }
                }
                if (sorted) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxRemain = 0;
        foreach (int remain in dp) {
            maxRemain = Math.Max(maxRemain, remain);
        }
        return m - maxRemain;
    }
}

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size(), m = strs[0].size();
        vector<int> dp(m, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < i; j++) {
                bool sorted = true;
                for (int k = 0; k < n && sorted; k++) {
                    if (strs[k][j] > strs[k][i]) {
                        sorted = false;
                    }
                }
                if (sorted) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxRemain = 0;
        for (int remain : dp) {
            maxRemain = max(maxRemain, remain);
        }
        return m - maxRemain;
    }
};

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n, m = len(strs), len(strs[0])
        dp = [1 for _ in range(m)]
        for i in range(1, m):
            for j in range(0, i):
                sorted = True
                for k in range(0, n):
                    if strs[k][j] > strs[k][i]:
                        sorted = False
                        break
                if sorted:
                    dp[i] = max(dp[i], dp[j] + 1)
        maxRemain = 0
        for remain in dp:
            maxRemain = max(maxRemain, remain)
        return m - maxRemain

复杂度分析

• 时间复杂度：$O(nm^2)$，其中 $n$ 是数组 $\textit{strs}$ 的长度，$m$ 是数组 $\textit{strs}$ 中每个字符串的长度。状态数是 $O(m)$，计算每个状态时需要遍历当前下标之前的 $O(m)$ 个下标，对于之前的每个下标需要 $O(n)$ 的时间判断之前的下标是否为当前下标的前驱下标，因此时间复杂度是 $O(nm^2)$。

• 空间复杂度：$O(m)$，其中 $m$ 是数组 $\textit{strs}$ 中每个字符串的长度。需要创建长度为 $m$ 的数组 $\textit{dp}$。