聊聊蚂蚁集团年终奖，附LeetCode 926题解法解析

开年回来，盼完了开工红包，大家就开始盘算年终奖了。毕竟绝大多数公司的年终奖都是年后派发，能在年前就开奖的，那可真是“良心企业”了。

之前我们聊过，年前发钱的大厂，一只手就数得过来，比如鹅厂、京东和快手。今天要说的这位主角，是在春节期间派发了上亿红包的阿里系——蚂蚁集团。

今年春节红包大战，阿里千问和蚂蚁阿福都下了血本。阿里千问直接送25元免单券，蚂蚁阿福则派发16.8元的支付宝无门槛红包，格局一下就和别人区分开了。业务上这么舍得烧钱，那给自家员工的年终奖，想必也值得期待。

根据脉脉等多个渠道的爆料，今年蚂蚁集团的年终奖情况大致如下：

• 绩效 3.5（主流评级）：年终奖在2.5到3.5个月之间，没有普调涨薪，也没有期权。不过不同业务线（BU）差别挺大：国际业务、数字支付线普遍超过3个月，而支付宝业务线多在2.5个月左右。
• 绩效 3.5+：年终奖能拿到3.5到5.5个月，调薪幅度在5%到10%之间，还能拿到大约3000份期权。
• 绩效 3.75：年终奖范围是4.5到8个月，少数表现特别突出的能突破10个月，调薪幅度10%到20%，期权大约4000份。

综合来看，今年蚂蚁高绩效（3.5以上）员工的奖金包，相比去年普遍有提升，尤其是3.75档位的，空间大了不少。

好了，八卦聊完，咱们程序员还是得回归本职工作。擦擦羡慕的眼泪，来看一道和“阿里巴巴”相关的算法题。

题目描述

平台：LeetCode
题号：926

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是单调递增的。

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0。

返回使 s 单调递增的最小翻转次数。

示例 1：

输入：s = “00110”
输出：1
解释：翻转最后一位得到 00111。

示例 2：

输入：s = “010110”
输出：2
解释：翻转得到 011111，或者是 000111。

示例 3：

输入：s = “00011000”
输出：2
解释：翻转得到 00000000。

提示：

• 1 <= s.length <= 10^5
• s[i] 为 '0' 或 '1'

LIS 问题贪心解

根据题意，我们可以做一个巧妙的等价转换：令 s 长度为 n，原问题等价于在 s 中找到最长不下降子序列，设其长度为 ans，那么对应的 n - ans 即是答案。

由于数据范围达到了 10^5，因此我们需要使用 LIS（最长递增子序列）问题的贪心求解方式：使用 g 数组记录每个长度的最小结尾元素，即 g[len] = x 含义为长度为 len 的最长不下降子序列的结尾元素为 x，然后在从前往后处理每个 t 时，由于是求解「最长不下降子序列」，等价于找「满足大于 t 的最小下标」，这可以运用「二分」进行求解。

不了解 LIS 问题或者不清楚 LIS 问题贪心解法的同学可以看前置知识：LCS 问题与 LIS 问题的相互关系，以及 LIS 问题的最优解证明，里面详细讲解了 LIS 贪心解的正确性证明，以及 LCS 和 LIS 在特定条件下存在的内在联系。

Java 代码：

class Solution {
    public int minFlipsMonoIncr(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length, ans = 0;
        int[] g = new int[n + 10];
        Arrays.fill(g, n + 10);
        for (int i = 0; i < n; i++) {
            int t = s.charAt(i) - '0';
            int l = 1, r = i + 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (g[mid] > t) r = mid;
                else l = mid + 1;
            }
            g[r] = t;
            ans = Math.max(ans, r);
        }
        return n - ans;
    }
}

C++ 代码：

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.length(), ans = 0;
        vector<int> g(n + 10, n + 10);
        for (int i = 0; i < n; i++) {
            int t = s[i] - '0';
            int l = 1, r = i + 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (g[mid] > t) r = mid;
                else l = mid + 1;
            }
            g[r] = t;
            ans = max(ans, r);
        }
        return n - ans;
    }
};

Python 代码：

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        n, ans = len(s), 0
        g = [n + 10] * (n + 10)
        for i in range(n):
            t = int(s[i])
            l, r = 1, i + 1
            while l < r:
                mid = l + r >> 1
                if g[mid] > t:
                    r = mid
                else:
                    l = mid + 1
            g[r] = t
            ans = max(ans, r)
        return n - ans

TypeScript 代码：

function minFlipsMonoIncr(s: string): number {
    let n = s.length, ans = 0;
    const g = new Array(n + 10).fill(n + 10);
    for (let i = 0; i < n; i++) {
        const t = parseInt(s[i]);
        let l = 1, r = i + 1;
        while (l < r) {
            const mid = l + r >> 1;
            if (g[mid] > t) r = mid;
            else l = mid + 1;
        }
        g[r] = t;
        ans = Math.max(ans, r);
    }
    return n - ans;
};

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)

前缀和 + 枚举

更进一步，利用 s 只存在 0 和 1 两种数值，我们知道最后的目标序列只可能形如 000...000、000...111 或 111...111。

因此我们可以枚举目标序列的 0 和 1 分割点位置 i（分割点是 0 是 1 都可以，不消耗改变次数）。

问题就转化为：分割点 i 左边有多少个 1（需要翻成 0），分割点 i 的右边有多少个 0（需要翻成 1），两者之和就是分割点为 i 时的总翻转次数。 枚举所有 i 并取最小值即是答案。

而高效求解某个点左边或右边有多少个 1 和 0，可以通过预处理「前缀和」来优化。

Java 代码：

class Solution {
    public int minFlipsMonoIncr(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length, ans = n;
        int[] sum = new int[n + 10];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (cs[i - 1] - '0');
        for (int i = 1; i <= n; i++) {
            int l = sum[i - 1];
            int r = (n - i) - (sum[n] - sum[i]);
            ans = Math.min(ans, l + r);
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.length(), ans = n;
        vector<int> sumv(n + 10, 0);
        for (int i = 1; i <= n; i++) sumv[i] = sumv[i - 1] + (s[i - 1] - '0');
        for (int i = 1; i <= n; i++) {
            int l = sumv[i - 1], r = (n - i) - (sumv[n] - sumv[i]);
            ans = min(ans, l + r);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        n, ans = len(s), len(s)
        sumv = [0] * (n + 10)
        for i in range(1, n + 1):
            sumv[i] = sumv[i - 1] + int(s[i - 1])
        for i in range(1, n + 1):
            l, r = sumv[i - 1], (n - i) - (sumv[n] - sumv[i])
            ans = min(ans, l + r)
        return ans

TypeScript 代码：

function minFlipsMonoIncr(s: string): number {
    let n = s.length, ans = n;
    const sumv = new Array(n + 10).fill(0);
    for (let i = 1; i <= n; i++) sumv[i] = sumv[i - 1] + parseInt(s[i - 1]);
    for (let i = 1; i <= n; i++) {
        const l = sumv[i - 1], r = (n - i) - (sumv[n] - sumv[i]);
        ans = Math.min(ans, l + r);
    }
    return ans;
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

最后

不管是关心大厂薪资动态，还是想精进算法解法，持续学习和交流都很有必要。如果你在刷题或面试求职的路上有什么心得或困惑，欢迎到云栈社区和更多开发者一起聊聊。那里不仅有技术干货，也有关于职业发展的真实讨论。

---

友情提示：巨划算的 LeetCode 会员优惠通道目前仍可用。
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周。