支付宝

支付宝昨天（2024-01-16）的无差别"送钱"的事儿，大家都知道了吧。

具体的，就是在昨天 14:40~14:45 期间，所有支付宝的支付订单都被减免了 20%，减免原因在界面上显示为"政府补贴"。

这里指的订单，是指所有通过支付宝产生的交易，包括「购物、信用卡、生活缴费、个人转账」等等，而且和此前（消费类的）有减免上限的政府补贴不同，本次减免无上限，统统 20%。

好家伙，个人转账 5W 减免 1W，那些刚好在那段时间有大额支付的幸运儿，你能想象他们多开心吗 🤣🤣🤣🤣

如此重大的 P0 事故（互联网公司对线上事故的评级，代表事故最高等级），虽然只有短短的 5 分钟，但如果被反应快又别有用心的不法分子利用上（同一笔钱，两个账号来回转），那就可不是一点羊毛的事儿，可能几十上万上百万，整条羊村都被薅走了。

正当所有人都觉得支付宝一定会或多或少有"追回"行动时，凌晨一则来自「支付宝官方微博」的公告说明来了：

简单总结的话：错误在支付宝一方，给出的优惠不会再追回。

好家伙，这属于是给这小部分的幸运儿发"过年费"了 🍋🍋🍋

虽然犯的是如此低级的错误，不像大公司所为，但处理方案又是实打实的"有格局"。搞得我都不好意思笑支付宝"草台班子、降本增笑"了 🤣🤣🤣

从本次的处理方案来看，我们可以做一些合理的猜测：

从这个发布声明的时间点来看，不难猜测，对于这次事故，支付宝经过了「修正模板 -> 统计事故损失金额 -> 事件逐级上报到高层 -> 高层决议最后处理方案 -> 将处理方案下发对应部门 -> 公关拟对外声明 -> 走声明审批流程 -> 正式发出」等多步环节，导致了声明发出的时间已经接近凌晨一点。

由于声明中涉及「提醒大家不要点击诈骗短信/链接」，因此必然不存在支付宝故意推迟声明时间的可能性，他们从事故到发声明，确实就是花了 10+ 小时。

另外，关于支付宝损失金额的猜测。

如果简单结合数据来看，这个数字会很大。

根据易观分析报告的公开数据，支付宝 2024 年第一季度的交易量为 118.19 万亿元，即每个月 39.4 万亿，折合每天约 1.31 万亿，每小时约 0.0546 万亿，每分钟约 9.1 亿。

事故维持 5 分钟，减免力度为 20%，就当全部订单都是不符合"政府补贴"要求的支付订单，那么损失金额约 $9.1 \times 5 \times 0.2 = 9.1$9.1×5×0.2=9.1 亿。

但实际情况并不会如此直接了当，支付订单的流量也不可能是均摊每天，甚至是每分钟。

从日期来说，1-16 是一个没有节日加成的普通周四；从时间点来说，14:40~14:45 虽然属于"白天"范畴，但也不是什么支付高峰期。

我问了在支付宝工作的朋友，他跟我分享道：一整周里的交易，会有接近一半的交易流水，会在周末假期产生；而如果是周内的工作日的话，会有 8 成的流水会在上班时间（09:00~18:00）以外的时间段产生。

基于此，虽然没有具体数字，同时事故维持时间段（5 分钟），不考虑传播效应导致的交易激增。可以合理推算 2025-01-16 14:40~14:45 产生的交易最多不会超过 20 亿，即亏损最多不会超过 4 亿。相比于简单线性均摊的 9.1 亿，还是要小不少的。

支付宝（蚂蚁金服）是一家全年净利润 238.2 亿的公司，4 个亿的事故，还是支付得起的，只不过导致事故发生的员工和部门，估计要面临大处罚了。

对此，你怎么看？昨天有薅到支付宝的羊毛吗？欢迎评论区交流。

...

回归主题。

来一道和「阿里（校招）」相关的算法题。

题目描述

平台：LeetCode

题号：406

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 $people[i] = [h_i, k_i]$people[i]=[hi​,ki​] 表示第 $i$i 个人的身高为 $h_i$hi​ ，前面 正好 有 $k_i$ki​ 个身高大于或等于 $h_i$hi​ 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 $queue[j] = [h_j, k_j]$queue[j]=[hj​,kj​] 是队列中第 $j$j 个人的属性（$queue[0]$queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

• $1 <= people.length <= 2000$1<=people.length<=2000
• $0 <= h_i <= 10^6$0<=hi​<=106
• $0 <= k_i < people.length$0<=ki​<people.length
• 题目数据确保队列可以被重建

构造 + 二分 + 树状数组

这是一道非常综合的题目。

首先根据双关键字排序：当「高度（第一维）」不同，根据高度排升序，对于高度相同的情况，则根据「编号（第二维）」排降序。

采取这样的排序规则的好处在于：在从前往后处理某个 $people[i]$people[i] 时，我们可以直接将其放置在「当前空位序列（从左往后统计的，不算已被放置的位置）」中的 $people[i][1] + 1$people[i][1]+1 位（预留了前面的 $people[i][1]$people[i][1] 个位置给后面的数）。

关于「空位序列」如图所示（黄色代表已被占用，白色代表尚未占用）：

具体的，我们按照构造的合理性来解释双关键字排序的合理性，假设当前处理的是 $people[i]$people[i]：

根据「高度」排升序，根据「编号」排降序：由于首先是根据「高度」排升序，因此当 $people[i]$people[i] 被放置在「当前空位序列」的第 $people[i][1] + 1$people[i][1]+1 之后，无论后面的 $people[j]$people[j] 如何放置，都不会影响 $people[i]$people[i] 的合法性：后面的数的高度都不低于 $people[i][0]$people[i][0]，无论放在 $people[i][1] + 1$people[i][1]+1 前面还是后面都不会影响 $people[i]$people[i] 的合法性。

同时对于高度（第一维）相同，编号（第二维）不同的情况，我们进行了「降序」处理，因此「每次将 $people[i]$people[i] 放置在空白序列的 $people[i][1] + 1$people[i][1]+1 位置的」的逻辑能够沿用：

对于「高度」相同「编号」不同的情况，会被按照「从右到左」依次放置，导致了每个 $people[i]$people[i] 被放置时，都不会受到「高度」相同的其他 $people[j]$people[j] 所影响。换句话说，当 $people[i]$people[i] 放置时，其左边必然不存在其他高度为 $people[i][0]$people[i][0] 的成员。

剩下的在于，如何快速找到「空白序列中的第 $k$k 个位置」，这可以通过「二分 + 树状数组」来做：

对于已被使用的位置标记为 $1$1，未使用的位置为 $0$0，那么第一个满足「$0$0 的个数大于等于 $k + 1$k+1」的位置即是目标位置，在长度明确的情况下，求 $0$0 的个数和求 $1$1 的个数等同，对于位置 $x$x 而言（下标从 $1$1 开始，总个数为 $x$x），如果在 $[1, x]$[1,x] 范围内有 $k + 1$k+1 个 $0$0，等价于有 $x - (k + 1)$x−(k+1) 个 $1$1。

求解 $[1, x]$[1,x] 范围内 $1$1 的个数等价于求前缀和，即「区间查询」，同时我们每次使用一个新的位置后 ，需要对其进行标记，涉及「单点修改」，因此使用「树状数组」进行求解。

Java 代码：

class Solution {
    int n;
    int[] tr;
    int lowbit(int x) {
        return x & -x;
    }
    void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    public int[][] reconstructQueue(int[][] ps) {
        Arrays.sort(ps, (a, b)->{
            return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];
        });
        n = ps.length;
        tr = new int[n + 1];
        int[][] ans = new int[n][2];
        for (int[] p : ps) {
            int h = p[0], k = p[1];
            int l = 1, r = n;
            while (l < r) {
                int mid = l + r >> 1;
                if (mid - query(mid) >= k + 1) r = mid;
                else l = mid + 1;
            }
            ans[r - 1] = p;
            add(r, 1);
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int n;
    vector<int> tr;
    int lowbit(int x) {
        return x & -x;
    }
    void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& ps) {
        sort(ps.begin(), ps.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] != b[0] ? a[0] < b[0] : b[1] < a[1];
        });
        n = ps.size();
        tr.resize(n + 1, 0);
        vector<vector<int>> ans(n, vector<int>(2));
        for (auto& p : ps) {
            int h = p[0], k = p[1];
            int l = 1, r = n;
            while (l < r) {
                int mid = l + r >> 1;
                if (mid - query(mid) >= k + 1) r = mid;
                else l = mid + 1;
            }
            ans[r - 1] = p;
            add(r, 1);
        }
        return ans;
    }  
};

Python 代码：

class Solution:
    def __init__(self):
        self.n = 0
        self.tr = []

    def lowbit(self, x):
        return x & -x

    def add(self, x, v):
        while x <= self.n:
            self.tr[x] += v
            x += self.lowbit(x)

    def query(self, x):
        ans = 0
        while x > 0:
            ans += self.tr[x]
            x -= self.lowbit(x)
        return ans

    def reconstructQueue(self, ps: List[List[int]]) -> List[List[int]]:
        ps.sort(key=lambda x: (x[0], -x[1]))
        self.n = len(ps)
        self.tr = [0] * (self.n + 1)
        ans = [[0, 0] for _ in range(self.n)]
        for p in ps:
            h, k = p
            l, r = 1, self.n
            while l < r:
                mid = l + r >> 1
                if mid - self.query(mid) >= k + 1:
                    r = mid
                else:
                    l = mid + 1
            ans[r - 1] = p
            self.add(r, 1)
        return ans

TypeScript 代码：

let n: number;
let tr: number[];
function lowbit(x: number): number {
    return x & -x;
}
function add(x: number, v: number): void {
    for (let i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
function query(x: number): number {
    let ans = 0;
    for (let i = x; i > 0; i -= lowbit(i)) ans += tr[i];
    return ans;
}
function reconstructQueue(ps: number[][]): number[][] {
    ps.sort(((a, b) => {
        return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];
    }));
    n = ps.length;
    tr = new Array(n + 1).fill(0);
    const ans = new Array(n).fill([0, 0]);
    for (const p of ps) {
        const [h, k] = p;
        let l = 1, r = n;
        while (l < r) {
            const mid = l + r >> 1;
            if (mid - query(mid) >= k + 1) r = mid;
            else l = mid + 1;
        }
        ans[r - 1] = p;
        add(r, 1);
    }
    return ans;
};

• 时间复杂度：排序的复杂度为 $O(n\log{n})$O(nlogn)；共要处理 $n$n 个 $people[i]$people[i]，每次处理需要二分，复杂度为 $O(\log{n})$O(logn)；每次二分和找到答案后需要操作树状数组，复杂度为 $O(\log{n})$O(logn)。整体复杂度为 $O(n \times \log{n} \times \log{n})$O(n×logn×logn)
• 空间复杂度：$O(n)$O(n)