今日头条实习面试算法题总结

算法题一

题目描述

输入一个长度为$n$的整型数组($1 \leq n \leq 10^8$),对数组中的每个元素,求其右侧第一个比它大的元素值。若其右侧没有比它大的值,输出-1。

测试样例

测试样例一

输入:[1, 2, 3, 4, 5]
输出:[2, 3, 4, 5, -1]

测试样例二

输入:[4, 3, 2, 1, 5]
输出:[5, 5, 5, 5, -1]

测试样例三

输入:[4, 1, 2, 3, 5, 6]
输出:[5, 2, 3, 5, 6, -1]

解题思路

如下图所示,可以将数组想像成从左向右排列的楼房,每个元素的大小代表着相应楼房的高矮。基于这一想法,可以将本题转化为对每栋楼求右侧第一栋比它高的楼。当我们站在一栋楼的楼顶(图中黄色)向右侧平视时,只能看到比它更高的楼(图中蓝色),同时高楼之间的矮楼会被挡住(图中灰色),因此只需要想办法在每个元素右侧维护这样一个递增的高楼序列(图中蓝色)即可。

1.png

因为需要向右侧维护这样一个序列,因此可以考虑从右向左对数组进行遍历,同时使用一个栈来保存右侧的高楼序列。如下图所示,对于每个元素,首先将栈中不大于它的元素逐个出栈,然后观察栈是否为空:若栈为空则右侧没有比它大的元素(返回-1),若栈非空则栈顶元素是右侧每一个比它大的元素,最后将当前元素添加到栈顶。

2.png

如下图所示,当走到元素5时,栈中元素分别为[4, 6, 7],首先将栈顶元素4出栈,然后发现栈顶元素6比当前值5大,因此右侧第一个比它大的值为6,同时将当前值5加入到栈中。然后走到元素3时,栈中元素分别为[5, 6, 7],栈顶元素比当前元素值大,因此元素3右侧第一个比它大的值为5,同时将当前值3加入到栈中。

3.png

因为对整个数组只遍历了一遍,且每个元素只会入栈并出栈一次,因此该算法整体的时间复杂度为$O(n)$。

解题代码

1
2
3
4
5
6
7
8
void solve(const int *a, int * res, const int len) {
std::stack<int> st;
for (int i = len - 1; i >= 0; i--) {
while (!st.empty() && st.top() <= a[i]) { st.pop(); }
res[i] = st.empty() ? -1 : st.top();
st.push(a[i]);
}
}

算法题二

题目描述

输入一个长度为$n$的非负整型数组$a$($1 \leq n \leq 10^8$),对于每个子数组$a[i..j]$($i \leq j$),定义函数:$f(i,j)=min(a[i..j]) * \sum_{k=i}^{j}a[k]$。请在数组$a$中找到一个子数组$a[i..j]$,使函数$f(i,j)$的值最大,并返回这个最大值。

测试样例

测试样例一

输入:[1, 2, 3, 4, 5]
输出:36([3, 4, 5])

测试样例二

输入:[2, 0, 3, 1, 4, 6, 5]
输出:60([4, 6, 5])

解题思路

$O(n^2)$解题思路

由函数$f(i,j)$的定义可知,本题中主要需解决两个问题:

  1. 对于子数组$a[i..j]$,快速求出所有元素的和
    通过计算前缀和数组,可以在$O(n)$时间复杂度内完成预处理,后续查询时间复杂度$O(1)$
  2. 对于子数组$a[i..j]$,快速求出所有元素的最小值
    基于ST Table(参见《ACM国际大学生程序设计竞赛-算法与实现》4.9节),可以在$O(nlogn)$时间复杂度内完成预处理,后续查询时间复杂度$O(1)$

以上两个问题经预处理后,都可以实现在$O(1)$时间复杂度内查询到答案,但我们仍需要遍历每一个子数组$a[i..j]$,因此算法整体的时间复杂度为$O(n^2)$,并不能满足本题数据量的要求。

$O(n)$解题思路

如果枚举每个子数组来查找最大值,需要的时间复杂度一定会上升到$O(n^2)$,因此需要转换一种枚举策略:将数组中的每个元素$a[k]$作为最小值,找到一个最大的区间$a[i..j]$($i \leq k \leq j$),使得区间内的每个值都不小于$a[k]$。

基于第一题的方法,可以想到如下的预处理策略:对于数组$a$,使用$O(n)$时间计算出辅助数组$left$和$right$,其中$left[k]$保存$a[k]$左侧第一个比它小的值的下标,若不存在则赋值为-1;$right[k]$保存$a[k]$右侧第一个比它小的值的下标,若不存在则赋值为-1。经过预处理之后,就可以在$O(1)$时间复杂度内找到每个元素$a[k]$对应的最大区间,并在$O(1)$时间复杂度内通过前缀和数组求出区间和,因此算法的整体时间复杂度为$O(n)$。

解题代码($O(n)$)

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
#define FIND_LEFT 1
#define FIND_RIGHT -1
void gene(const int *a, int * res, const int len, const int step = FIND_RIGHT) {
std::stack<int> st;
const int begin = step == FIND_RIGHT ? len - 1 : 0;
const int end = step == FIND_RIGHT ? 0 : len;
for (int i = begin; i != end; i += step) {
while (!st.empty() && a[st.top()] >= a[i]) { st.pop(); }
res[i] = st.empty() ? -1 : st.top();
st.push(i);
}
}
int solve(const int *a, const int len) {
int *sum = new int[len];
sum[0] = a[0];
for (int i = 1; i < len; i++) { sum[i] = sum[i - 1] + a[i]; }
int *left = new int[len], *right = new int[len];
gene(a, left, len, FIND_LEFT);
gene(a, right, len, FIND_RIGHT);
int ans = 0;
for (int i = 0; i < len; i++) {
int left_sum = left[i] == -1 ? 0 : sum[left[i]];
int right_sum = sum[right[i] == -1 ? len - 1 : right[i] - 1];
int res = a[i] * (right_sum - left_sum);
ans = std::max(res, ans);
}
return ans;
}