B站2021校招笔试题，这样的算法有点难

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天我们来看B站2021年校招笔试题当中的一道算法题，算是很有意思，也有一定的难度。

题目来源于牛客网，感兴趣的同学可以点击阅读原文跳转。

题面

小明最近喜欢上了俄罗斯套娃、大鱼吃小鱼这些大的包住小的类型的游戏。

于是小明爸爸给小明做了一个特别版的大鱼吃小鱼游戏，他希望通过这个游戏能够近一步提高牛牛的智商。

游戏规则如下：

现在有N条鱼，每条鱼的体积为Ai，从左到右排成一排。

A数组是一个排列。

小明每轮可以执行一次大鱼吃小鱼的操作

一次大鱼吃小鱼的操作：对于每条鱼，它在每一次操作时会吃掉右边比自己小的第一条鱼

值得注意的是，在一次操作中，每条鱼吃比自己小的鱼的时候是同时发生的。

举一个例子，假设现在有三条鱼,体积为分别[5，4，3]，5吃4，4吃3，一次操作后就剩下[5]一条鱼。

爸爸问小明，你知道要多少次操作，鱼的数量就不会变了嘛？

输入描述:

给定N；给定A数组１＜＝N＜＝10^5,１＜＝Ai＜＝Ｎ

输出描述:

一行, 正整数, 表示要多少次操作，鱼的数量就不会变了。

输入例子1:

3
1 2 3

输出例子1:

0

输入例子2:

6
4 3 2 3 2 1

输出例子2:

2

例子说明2:

[4,3,2,3,2,1]-->[4,3]-->[4]

分析

还是老套路，我们拿到题目先来分析一下题目，看看题目当中有没有遗漏或者是隐藏的一些信息。

首先可以发现的是，题目中说了每条鱼是同时进食的，也就是说同一时间会有多条鱼被吃掉。比如第二个样例当中：4,3,2，在第一次进食之后，就只剩下了4，因为2被3吃，3被4吃，这些都是同时发生的。

那么进而我们可以得知，在一次进食之后，一个下降的序列会只剩下一个数，也就是最大的那个。

其次，我们可以发现如果某条鱼右边的与比它大的话，那么它是无法进食的。虽然题目当中说了，每条鱼会选择右侧最近的比它小的鱼进行进食，但如果它右侧的鱼比它大的话，这个食物会被抢夺。比如4,5,3，对于4来说，3是它的食物，但由于5比4大，3同样也会是5的食物。

虽然题目中并没有明说这种情况到底应该算是谁吃的，但从解题的角度出发，算是5的食物会比较简单，因为3和5挨着，判断起来更加容易。这样分析之后，我们可以挖掘出一个比较有用的结论：我们只需要考虑邻近鱼之间的关系。

有了这个结论之后，很容易可以构想出暴力的解法：我们每次删除整条递减序列，依次迭代，直到不会发生变更为止：

int solve(int n, vector<int>& nums) {
    int ret = 0;
    // 存放能够存活到下一轮的鱼
    vector<int> nxt;
    while (true) {
        nxt.clear();
        // 判断是否会发生变更
        bool flag = true;
        n = nums.size();
        nxt.push_back(nums[0]);
        // 记录上一条鱼的大小
        int last = nums[0];
        for (int i = 1; i < n; i++) {
            // 如果当前鱼小于上一条，那么会被吃
            if (nums[i] < last) {
                // 更新last
                last = nums[i];
                flag = false;
            // 否则不会被吃，会进入下一轮，存入nxt当中
            }else {
                last = nums[i];
                nxt.push_back(nums[i]);
            }
        }
        // 没有发生变更
        if (flag) break;
        nums = nxt;
        ret++;
    }
    return ret;
}

这种做法比较容易想到，代码也不算难写，但是当中有一个很大的问题，就是复杂度。

暴力求解的最坏复杂度是O(n^2) ，我们很容易举出一个例子，比如4,3,3,3,3,3,3,3。由于除了第一条鱼之外其他鱼的大小都相等，相等的鱼无法吞食。所以对于这样的数据，一定要执行n轮，每一轮被第一条鱼吞吃一条。由于每一轮都需要遍历所有剩下的鱼，那么自然复杂度是O(n^2) 。

由于题目当中明确说了n最大是10^5 ，那么在O(n^2) 这个量级下是一定会超时的。

不过可惜的是牛客网的数据比较弱，只有五组数据，采用暴力的方法一样能通过。更夸张的是，牛客网中的题解都是基于暴力做的……

正解

在我们公布正解之前，依然需要首先分析题目。

我们可以考虑一些通用的状态，比如假设，我们已经知道对于某一条鱼x来说，假设要经过k轮，它才能达到稳定状态，也就是把所有能吃的鱼都吃了。那么显然，对于x来说，如果有一条鱼能够吃掉x，至少也需要k轮才能稳定。

其次我们考虑多条鱼吞吃的情况，比如某一个状态下剩下三条鱼：4,3,3，对于4来说，它要吃掉右侧的两个3才能到达稳定。假设第一个3是经过两轮到达稳定的（例如3,2,1,2），那么根据我们上面的结论，4吞食掉它也需要两轮（4,3,2,1,2）。也就是说两轮之后达到状态4,3，还额外需要一轮才能稳定。

我们可以考虑维护每条鱼到达稳定状态时需要的时间，如果我们从左往右遍历，由于无法预知右侧的鱼的大小，所以很难第一时间判断当前的鱼是否到达稳定。可以考虑反向操作，我们从右往左遍历，由于右侧的鱼大小已经确定，所以我们可以立即确定当前鱼的情况。

如果当前鱼比右侧鱼更大，那么直接吞吃，维护所需的时间。如果当前鱼更小，无法吞吃，那么需要记录下来，因为左侧可能有更大的鱼。这样一来，我们记录数组中的鱼一定是递减的，很容易想到，这其实是一个单调栈。

当前的鱼更大时，需要吞吃栈中的鱼，由于栈中的鱼是递增的，这是达到稳定的最终状态，它们之间不会再发生吞吃。所以只需要考虑当前鱼吞吃的情况。我们考虑当前栈中被吞吃的鱼是ABC，它们所需要稳定的轮数分别是abc。那么吞吃A时，所需要的时间是max(1, a)，吞吃B时，所需要的时间是max(max(1, a)+1, b)，吞吃C时，所需要的时间是max(max(max(1, a)+1, b)+1, c)。

这个式子看起来有些复杂， 我们用伪代码展示就是：

tmp = 0
for t in [a, b, c]:
    tmp = max(tmp+1, t)

tmp存的是吞吃当前鱼之前所需要的时间，由于吞吃当前鱼本身需要单位1的时间，并且吞吃是同步发生的，如果当前鱼稳定需要的t很大，可能当前鱼在稳定之前就已经被吃了，所以取的是max(tmp+1, t)。

我们把这些思路全部厘清之后，其实答案就很简单了，我们只需要倒序遍历，维护一个单调栈即可。

typedef pair<int, int> pii;
    
int solve(int n, vector<int>& nums) {
    // 使用vector模拟栈，vector元素为pair<int, int> first存鱼的大小，second存鱼稳定需要的时间
    vector<pii> sta;
    int ret = 0;
    for (int i = n-1; i > -1; i--) {
        int tmp = 0;
        // 如果i更大，则吞吃sta中的鱼，直到吃不下为止
        while (sta.size() > 0 && nums[i] > sta.back().first) {
            tmp = max(tmp+1, sta.back().second);
            sta.pop_back();
        }
        // 将当前鱼压入栈
        sta.push_back(make_pair(nums[i], tmp));
        ret = max(ret, tmp);
    }
    return ret;
}

又是一道单调栈的题，单调栈这个数据结构本身并不难，很好理解， 就是一个栈，只不过元素有单调性。但涉及它的问题往往思路比较曲折，需要转好几个弯才能联想到单调栈，所以从这个角度来说，想要把单调栈的问题做好还挺难的，需要我们多多练习。

好了，关于这道题就先聊到这里，感谢大家的阅读。