公司裁员时，老板认为技术总监薪资过高便将其辞退。不料总监一走，整个研发部门迅速陷入瘫痪，各项项目全面停摆。。

刚看到个贴子，说一家公司裁员时，老板嫌技术总监薪资太高就直接辞了人。结果总监一走，整个研发部门直接瘫痪，项目全停。最后老板不得不以双倍工资把人请回。

真是活生生的“省小钱亏大本”。网友有人笑说“老板是花两倍的学费学了个教训”，我挺认同的。职场里最怕的不是员工贵，而是看不懂谁真正创造价值。能稳住局面、搭起架构、带着团队跑的人，那不是成本，是核心资产。

换个角度想，优秀人才的价值，不在工时，而在系统。没有他们，企业就像没舵的船，往哪儿漂都靠运气。老板精明可以，但不能短视。

真正懂管理的人，永远不会拿骨干的工资动刀。因为你砍掉的，往往不是薪资，是企业的未来。【备注:文末可领最新资料】

算法题：修改列

昨天晚上十一点多，在公司楼下吹风，手里拿着还温的奶茶，群里有人@我说“东哥那个修改列怎么写啊，用 Java 的”。我一听这名儿…别想太复杂，就是那个——给你一堆等长字符串，按列看，每一列从上到下得是非递减（a≤b≤c这种），你可以把某些格子的字符改掉，代价是1次修改一个格子，问最少要改几下。嗯对，就这味儿。

你把输入想成一张表，m 行 n 列。第 j 列是一个长度为 m 的字符序列。我们不许换行顺序，只能改字符，让这一列从上到下不降。那最少改多少？直觉上你会想“把这列都改成同一个字母”，但不一定最省。省的办法是：保留一个“已经是非递减”的最长子序列，其他位置再改。这个最长非降子序列的长度，专业点叫 LNDS。列长度是 m，那这一列最少改 m − LNDS。全表的答案就是把每一列算一遍的和。对吧，很直给。

为啥是 LNDS？因为我们不能调换行，只能改字母。保留尽量多的“顺着升”的位置，剩下的都修正掉，代价最小。这跟经典的“最少修改使序列非降”是同一道题。计算 LNDS 有两招：O(m²) 的 DP 好写但慢；或者“牌堆法”（耐心排序思路）O(m log m)，列数多时更香。我这边直接上 O(m log m)，列里把字符转成整数（'a'..'z' 或直接 Unicode 码），跑非降 LIS 就行。哦对，是“非降”，所以二分边界用 upperBound 还是 lowerBound 要注意一下，我这写的是允许相等的版本。

import java.util.*;

publicclassModifyColumns{
// 计算一列的最少修改次数：m - LNDS
privatestaticintminChangeForColumn(char[] col){
// tails[k] 表示长度为 k+1 的非降子序列的最小可能结尾值
        ArrayList<Integer> tails = new ArrayList<>();
for (char ch : col) {
int x = ch; // 直接用字符的整数值做比较
// 找到第一个 > x 的位置，允许相等（非降），所以用 upperBound
int l = 0, r = tails.size();
while (l < r) {
int mid = (l + r) >>> 1;
if (tails.get(mid) <= x) { // <= 扩展非降
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
if (l == tails.size()) {
                tails.add(x);
            } else {
                tails.set(l, x);
            }
        }
int lnds = tails.size();
return col.length - lnds;
    }

// 主函数：给定 m 行字符串，统计总最少修改次数
publicstaticintminChanges(List<String> rows){
if (rows == null || rows.isEmpty()) return0;
int m = rows.size();
int n = rows.get(0).length();
// 简单健壮性：保证等长
for (String s : rows) {
if (s.length() != n) thrownew IllegalArgumentException("行长度不一致");
        }
int ans = 0;
// 构造每一列
for (int c = 0; c < n; c++) {
char[] col = newchar[m];
for (int r = 0; r < m; r++) col[r] = rows.get(r).charAt(c);
            ans += minChangeForColumn(col);
        }
return ans;
    }

// 小测一下
publicstaticvoidmain(String[] args){
        List<String> rows = Arrays.asList(
"abca",
"bbcb",
"bccd"
        );
// 你们可以自己改几组数据试试
        System.out.println(minChanges(rows)); // 打印最少修改次数
    }
}

等等我刚喝一口…回来继续。这个 upperBound 的点再强调一下。我们要“非降”，也就是允许相等，所以在二分里用 <= x 往右挪，等价于找第一个 > x 的位置放置，这样相等的会接在后面，保证子序列是 a≤a≤b 这种，不会误伤。要是你把条件写反了，很容易变成“严格上升”，答案就会偏大，别问为啥我知道…昨天小李就踩了。

字符集不是英文？没事，char 本身就是数，直接比。列很短？O(m²) 的 DP 更好写：dp[i] 是以 i 结尾的非降子序列长度，枚举 j<i 且 col[j]≤col[i] 更新，最后取 max，一列复杂度 m²，代码也就十来行。还有个小坑：输入空表或者只有一行，那最少修改肯定是 0，因为一列只有一个元素天然非降。嗯…差不多就这些，我去把奶茶吸完了，谁要是把“非降”和“非增”又搞混了，回去抄十遍，这个不改列也得改脑子，开个玩笑别打人啊。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html