天融信 2023 的年终奖。。

天融信

过去几天，最大的瓜，是天融信 2023 的年终奖脚踝砍。

"天融信"是国内首家网络安全企业，同时也是一家上市公司。

就在前些天，有网友爆料出，天融信年终奖到账只有几百元，甚至只有几十元：

一时间，「传天融信年终奖打折，到账几百元」冲上热搜，目前仍占领职场类 App 的热搜第一：

通常此类操作，如果是技术问题导致的搞错，到现在怎么都被辟谣了。

结果却越来越多网友参与到爆料中：

当中不少带着天融信企业认证的网友分享道，连几十元都没有，而是 0 元年终：

更离谱的是，这家搞网络安全的公司，0 元年终还专门发个短信通知一下，确实严谨。

对此，你怎么看？

...

回归主线。

来一道近期读者投稿，和「腾讯（社招二面）」相关的算法题。

题目描述

平台：LeetCode

题号：901

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来 7 天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

示例：

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]

输出：[null,1,1,1,2,1,4,6]

解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

提示：

调用 StockSpanner.next(int price) 时，将有。
每个测试用例最多可以调用 10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。

分块

又名优雅的暴力。

这是一道在线问题，在调用 next 往数据流存入元素的同时，返回连续段不大于当前元素的数的个数。

一个朴素的想法是：使用数组 nums 将所有 price 进行存储，每次返回时往前找到第一个不满足要求的位置，并返回连续段的长度。

但对于的调用次数来看，该做法的复杂度为，计算量为，不满足 OJ 要求。

实际上我们可以利用「分块」思路对其进行优化，将与连续段的比较转换为与最值的比较。

具体的，我们仍然使用 nums 对所有的 price 进行存储，同时使用 region 数组来存储每个连续段的最大值，其中含义为块编号为 loc 的最大值为 x，其中块编号 loc 块对应了数据编号 idx 的范围。

对于 next 操作而言，除了直接更新数据数组 nums[++idx] = price 以外，我们还需要更新 idx 所在块的最值 region[loc]，然后从当前块 loc 开始往前扫描其余块，使用 left 和 right 代指当前处理到的块的左右端点，若当前块满足 region[loc] <= price，说明块内所有元素均满足要求，直接将当前块 loc 所包含元素个数累加到答案中，直到遇到不满足的块或达到块数组边界，若存在遇到不满足要求的块，再使用 right 和 left 统计块内满足要求 nums[i] <= price 的个数。

对于块个数和大小的设定，是运用分块降低复杂度的关键，数的个数为，我们可以设定块大小为，这样也限定了块的个数为个。这样对于单次操作而言，我们最多遍历进行次的块间操作，同时最多进行一次块内操作，整体复杂度为，单次 next 操作计算量为以内，单样例计算量为，可以过。

为了方便，我们令块编号 loc 和数据编号 idx 均从开始；同时为了防止每个样例都 new 大数组，我们采用 static 优化，并在 StockSpanner 的初始化中做重置工作。

Java 代码：

class StockSpanner {
    static int N = 10010, len = 100, idx = 0;
    static int[] nums = new int[N], region = new int[N / len + 10];
    public StockSpanner() {
        for (int i = 0; i <= getIdx(idx); i++) region[i] = 0;
        idx = 0;
    }
    int getIdx(int x) {
        return (x - 1) / len + 1;
    }
    int query(int price) {
        int ans = 0, loc = getIdx(idx), left = (loc - 1) * len + 1, right = idx;
        while (loc >= 1 && region[loc] <= price) {
            ans += right - left + 1;
            loc--; right = left - 1; left = (loc - 1) * len + 1;
        }
        for (int i = right; loc >= 1 && i >= left && nums[i] <= price; i--) ans++;
        return ans;
    }
    public int next(int price) {
        nums[++idx] = price;
        int loc = getIdx(idx);
        region[loc] = Math.max(region[loc], price);
        return query(price);
    }
}

TypeScript 代码：

class StockSpanner {
    N: number = 10010; sz: number = 100; idx: number = 0
    nums: number[] = new Array<number>(this.N).fill(0);
    region = new Array<number>(Math.floor(this.N / this.sz) + 10).fill(0)
    getIdx(x: number): number {
        return Math.floor((x - 1) / this.sz) + 1
    }
    query(price: number): number {
        let ans = 0, loc = this.getIdx(this.idx), left = (loc - 1) * this.sz + 1, right = this.idx
        while (loc >= 1 && this.region[loc] <= price) {
            ans += right - left + 1
            loc--; right = left - 1; left = (loc - 1) * this.sz + 1
        }
        for (let i = right; loc >= 1 && i >= left && this.nums[i] <= price; i--) ans++
        return ans
    }
    next(price: number): number {
        this.nums[++this.idx] = price
        const loc = this.getIdx(this.idx)
        this.region[loc] = Math.max(this.region[loc], price)
        return this.query(price)
    }
}

Python3 代码：

class StockSpanner:
    def __init__(self):
        self.N, self.sz, self.idx = 10010, 110, 0
        self.nums, self.region = [0] * self.N, [0] * (self.N // self.sz + 10)

    def next(self, price: int) -> int:
        def getIdx(x):
            return (x - 1) // self.sz + 1

        def query(price):
            ans, loc = 0, getIdx(self.idx)
            left, right = (loc - 1) * self.sz + 1, self.idx
            while loc >= 1 and self.region[loc] <= price:
                ans += right - left + 1
                loc -= 1
                right, left = left - 1, (loc - 1) * self.sz + 1
            while loc >= 1 and right >= left and self.nums[right] <= price:
                right, ans = right - 1, ans + 1
            return ans

        self.idx += 1
        loc = getIdx(self.idx)
        self.nums[self.idx] = price
        self.region[loc] = max(self.region[loc], price)
        return query(price)

时间复杂度：由于使用了 static 优化， StockSpanner 初始化时，需要对上一次使用的块进行重置，复杂度为；由于块大小和数量均为， next 操作复杂度为
空间复杂度：

单调栈

另外一个容易想到的想法是使用「单调栈」，栈内以二元组形式维护比当前元素 price 大的元素。

每次执行 next 操作时，从栈顶开始处理，将所有满足「不大于 price」的元素进行出栈，从而找到当前元素 price 左边最近一个比其大的位置。

Java 代码：

class StockSpanner {
    Deque<int[]> d = new ArrayDeque<>();
    int cur = 0;
    public int next(int price) {
        while (!d.isEmpty() && d.peekLast()[1] <= price) d.pollLast();
        int prev = d.isEmpty() ? -1 : d.peekLast()[0], ans = cur - prev;
        d.addLast(new int[]{cur++, price});
        return ans;
    }
}

TypeScript 代码：

class StockSpanner {
    stk = new Array<Array<number>>(10010).fill([0, 0])
    he = 0; ta = 0; cur = 0
    next(price: number): number {
        while (this.he < this.ta && this.stk[this.ta - 1][1] <= price) this.ta--
        const prev = this.he >= this.ta ? -1 : this.stk[this.ta - 1][0], ans = this.cur - prev
        this.stk[this.ta++] = [this.cur++, price]
        return ans
    }
}

Python3 代码：

class StockSpanner:
    def __init__(self):
        self.stk = []
        self.cur = 0

    def next(self, price: int) -> int:
        while self.stk and self.stk[-1][1] <= price:
            self.stk.pop()
        prev = -1 if not self.stk else self.stk[-1][0]
        ans = self.cur - prev
        self.stk.append([self.cur, price])
        self.cur += 1
        return ans