无妄，往吉

0%

与TLE斗争到底系列（二）：双向扫描

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

今天做了一道2020腾讯校招技术笔试题目，难度不大，但同样容易诱导我们写出TLE的代码。为了优化时间复杂度，我们可以借助双向扫描来降低程序步数。对于双向扫描，顾名思义，以一维数组为例，从左到右遍历数组内部元素，我们视为一次单向扫描，那么，双向扫描即意味着从左到右遍历元素，而后从右到左遍历元素。如何借助双向扫描来降低时间复杂度呢？我们从一道题目开始：

逛街

小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。

小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

Simple Test Cases

Input

输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。
1<=n<=100000;
1<=wi<=100000;

1
2
6
5 3 8 3 2 5

Output

输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。

1
3 3 5 4 4 4

Limit

Time: C/C++ 2秒，其他语言4秒
Space: C/C++ 256M，其他语言512M

对于这道题，我们的第一直觉是遍历数组内部每一个元素，并向左和向右查找符合条件的元素，并输出结果，因此，很容易想到，其时间复杂度为$O(n^2)$ 。实践证明，暴力查找法只能够通过50%的测试数据集。

回到题目中来，对于当前位置i（$0 \leq i \leq n$），我们需要知道其左侧能够看到的建筑序列和右侧能够看到的建筑序列，也就是说，需要找到左侧的递增序列和右侧的递增序列。同时，对于每一栋建筑i，其左右两侧能够看到的建筑数量是独立的。因此，就左侧而言，我们可以维护一个小根堆，每遍历一个位置元素，即更新一次小根堆，其大小即是当前位置所能够看到的建筑数量，右侧同理。（注：相信大家也看出来了，这其实是一个单调栈。）左侧可视建筑数量加上右侧可视建筑数量并加上当前所在建筑，即是所有可视建筑数量。

再来看时间复杂度，采用双向扫描的方式，各维护一个单调栈，最后遍历每一个位置，并得到可视建筑数量，其时间复杂度为$O(n+n+n)$，即$O(n)$，比之$O(n^2)$更优。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

vector<int> watch(vector<int> &buildings, int n)
{
    vector<int> seen, left, right;

    //  小根堆
    priority_queue<int, vector<int>, greater<int>> front, back;
    
    // 从左向右扫描
    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            left.push_back(0);
            continue;
        }

        if (front.empty() || front.top() > buildings[i - 1]) {
            front.push(buildings[i - 1]);
            left.push_back(front.size());
            continue;
        }
		
        // 保持单调递增
        while (!front.empty() && front.top() <= buildings[i - 1]) {
            front.pop();
        }

        front.push(buildings[i - 1]);
        left.push_back(front.size());
    }

    // 从右往左扫描
    for (int i = n - 1; i >= 0; --i) {
        if (i == n - 1) {
            right.push_back(0);
            continue;
        }

        if (back.empty() || back.top() > buildings[i + 1]) {
            back.push(buildings[i + 1]);
            right.push_back(back.size());
            continue;
        }

        while (!back.empty() && back.top() <= buildings[i + 1]) {
            back.pop();
        }

        back.push(buildings[i + 1]);
        right.push_back(back.size());
    }

    for (int i = 0, j = n - 1; i < n && j >= 0; i++, j--) {
        seen.push_back(1 + left[i] + right[j]);
    }

    return seen;
}

int main()
{
    int n;
    cin >> n;

    vector<int> buildings;
    for (int i = 0; i < n; ++i) {
        int height;
        cin >> height;
        buildings.push_back(height);
    }

    vector<int> seen = watch(buildings, n);
    for (auto &s : seen) {
        cout << s << " ";
    }
    cout << endl;

    return 0;
}

以上！