登录从左到右贪心 + 优化（Python/Java/C++/Go）
例如 $\textit{strs}=[\texttt{ac},\texttt{ad},\texttt{ba},\texttt{bb}]$，竖着看就是
$$
\begin{aligned}
& \texttt{ac} \
& \texttt{ad} \
& \texttt{ba} \
& \texttt{bb} \
\end{aligned}
$$
第一列是升序，可以不删。
- 如果删第一列，那么需要完整地比较第二列的四个字母是不是升序。
- 如果不删第一列，那么对于第二列，由于 $\texttt{d}$ 和 $\texttt{a}$ 前面的字母不同，只看第一列的字母就能确定 $\texttt{ad} < \texttt{ba}$，所以我们不需要比较 $\texttt{d}$ 和 $\texttt{a}$ 的大小。此时第二列分成了两组 $[\texttt{c},\texttt{d}]$ 和 $[\texttt{a},\texttt{b}]$，只需判断组内字母是不是升序，而不是完整地比较第二列的四个字母。
由此可见，当列已经是升序时，不删更好，后面需要比较的字母更少，更容易满足要求，最终删除的列更少。
如果列不是升序，那么一定要删（否则最终得到的数组不是字典序排列）。
优化前
###py
class Solution:
def minDeletionSize(self, strs: List[str]) -> int:
n, m = len(strs), len(strs[0])
a = [''] * n # 最终得到的字符串数组
ans = 0
for j in range(m):
for i in range(n - 1):
if a[i] + strs[i][j] > a[i + 1] + strs[i + 1][j]:
# j 列不是升序，必须删
ans += 1
break
else:
# j 列是升序，不删更好
for i, s in enumerate(strs):
a[i] += s[j]
return ans
###java
class Solution {
public int minDeletionSize(String[] strs) {
int n = strs.length;
int m = strs[0].length();
String[] a = new String[n]; // 最终得到的字符串数组
Arrays.fill(a, "");
int ans = 0;
next:
for (int j = 0; j < m; j++) {
for (int i = 0; i < n - 1; i++) {
if ((a[i] + strs[i].charAt(j)).compareTo(a[i + 1] + strs[i + 1].charAt(j)) > 0) {
// j 列不是升序，必须删
ans++;
continue next;
}
}
// j 列是升序，不删更好
for (int i = 0; i < n; i++) {
a[i] += strs[i].charAt(j);
}
}
return ans;
}
}
###cpp
class Solution {
public:
int minDeletionSize(vector<string>& strs) {
int n = strs.size(), m = strs[0].size();
vector<string> a(n); // 最终得到的字符串数组
int ans = 0;
for (int j = 0; j < m; j++) {
bool del = false;
for (int i = 0; i < n - 1; i++) {
if (a[i] + strs[i][j] > a[i + 1] + strs[i + 1][j]) {
// j 列不是升序，必须删
ans++;
del = true;
break;
}
}
if (!del) {
// j 列是升序，不删更好
for (int i = 0; i < n; i++) {
a[i] += strs[i][j];
}
}
}
return ans;
}
};
###go
func minDeletionSize(strs []string) (ans int) {
n, m := len(strs), len(strs[0])
a := make([]string, n) // 最终得到的字符串数组
next:
for j := range m {
for i := range n - 1 {
if a[i]+string(strs[i][j]) > a[i+1]+string(strs[i+1][j]) {
// j 列不是升序，必须删
ans++
continue next
}
}
// j 列是升序，不删更好
for i, s := range strs {
a[i] += string(s[j])
}
}
return
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nm^2)$，其中 $n$ 是 $\textit{strs}$ 的长度，$m$ 是 $\textit{strs}[i]$ 的长度。比较 $\mathcal{O}(nm)$ 次大小，每次 $\mathcal{O}(m)$。
- 空间复杂度：$\mathcal{O}(nm)$。
优化
回顾前文的例子：
$$
\begin{aligned}
& \texttt{ac} \
& \texttt{ad} \
& \texttt{ba} \
& \texttt{bb} \
\end{aligned}
$$
第一列升序，不删。由于 $\textit{strs}[1][0] < \textit{strs}[2][0]$，后续 $a[1] < a[2]$ 必定成立，所以不需要比较这两个字符串。对于其余相邻字符串来说，由于第一列的字母都一样，所以只需比较第二列的字母，无需比较整个字符串。
怎么维护需要比较的下标（行号）呢？可以用哈希集合，或者布尔数组，或者创建一个下标列表，删除列表中的无需比较的下标。最后一种方法最高效，我们可以用 27. 移除元素 的方法，原地删除无需比较的下标，见 我的题解。
###py
class Solution:
def minDeletionSize(self, strs: List[str]) -> int:
n, m = len(strs), len(strs[0])
check_list = list(range(n - 1))
ans = 0
for j in range(m):
for i in check_list:
if strs[i][j] > strs[i + 1][j]:
# j 列不是升序，必须删
ans += 1
break
else:
# j 列是升序，不删更好
new_size = 0
for i in check_list:
if strs[i][j] == strs[i + 1][j]:
# 相邻字母相等，下一列 i 和 i+1 需要继续比大小
check_list[new_size] = i # 原地覆盖
new_size += 1
del check_list[new_size:]
return ans
###java
class Solution {
public int minDeletionSize(String[] strs) {
int n = strs.length;
int m = strs[0].length();
int size = n - 1;
int[] checkList = new int[size];
for (int i = 0; i < size; i++) {
checkList[i] = i;
}
int ans = 0;
next:
for (int j = 0; j < m; j++) {
for (int t = 0; t < size; t++) {
int i = checkList[t];
if (strs[i].charAt(j) > strs[i + 1].charAt(j)) {
// j 列不是升序，必须删
ans++;
continue next;
}
}
// j 列是升序，不删更好
int newSize = 0;
for (int t = 0; t < size; t++) {
int i = checkList[t];
if (strs[i].charAt(j) == strs[i + 1].charAt(j)) {
// 相邻字母相等，下一列 i 和 i+1 需要继续比大小
checkList[newSize++] = i; // 原地覆盖
}
}
size = newSize;
}
return ans;
}
}
###cpp
class Solution {
public:
int minDeletionSize(vector<string>& strs) {
int n = strs.size(), m = strs[0].size();
vector<int> check_list(n - 1);
ranges::iota(check_list, 0);
int ans = 0;
for (int j = 0; j < m; j++) {
bool del = false;
for (int i : check_list) {
if (strs[i][j] > strs[i + 1][j]) {
// j 列不是升序，必须删
ans++;
del = true;
break;
}
}
if (del) {
continue;
}
// j 列是升序，不删更好
int new_size = 0;
for (int i : check_list) {
if (strs[i][j] == strs[i + 1][j]) {
// 相邻字母相等，下一列 i 和 i+1 需要继续比大小
check_list[new_size++] = i; // 原地覆盖
}
}
check_list.resize(new_size);
}
return ans;
}
};
###go
func minDeletionSize(strs []string) (ans int) {
n, m := len(strs), len(strs[0])
checkList := make([]int, n-1)
for i := range checkList {
checkList[i] = i
}
next:
for j := range m {
for _, i := range checkList {
if strs[i][j] > strs[i+1][j] {
// j 列不是升序，必须删
ans++
continue next
}
}
// j 列是升序，不删更好
newCheckList := checkList[:0] // 原地
for _, i := range checkList {
if strs[i][j] == strs[i+1][j] {
// 相邻字母相等，下一列 i 和 i+1 需要继续比大小
newCheckList = append(newCheckList, i)
}
}
checkList = newCheckList
}
return
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{strs}$ 的长度，$m$ 是 $\textit{strs}[i]$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$。
专题训练
见下面贪心题单的「§1.4 从最左/最右开始贪心」。
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
