前言
大家好，我是程序员吴哥。
这两天有同学给我发来信息。
他提到了字节跳动国际电商第三次面试时遇到的一道算法题。
我搜索过这个问题，但没找到。
因此，我赶紧把这个原始问题分享给大家。
标题描述
找出数组中大于左侧元素且小于右侧元素的元素，并返回这些元素的索引
所需时间复杂度
输入：[2, 3, 1, 8, 9, 20, 12]
输出：3、4
解释：数组中的 8 和 9 符合题目要求，它们的索引分别是 3 和 4。
问题分析
最简单的想法就是遍历数组，正向和反向遍历每个元素，看是否满足条件。
伪代码如下
for(int i = 0; i < n; i ++) {
for(int j = 0; j < i; j ++) {
//左侧是否都比它小
}
for(int k = j + 1; k < n; k ++) {
//右侧是否都比它大
}
//若两条件均满足则记录下来
}
这个解法不符合题目要求。
正如题目要求，外循环无法优化，有什么办法可以优化内循环吗？
一些！
通过分析可以得出，对于每个元素，如果它大于左边的最大值，并且小于右边的最小值，则满足条件。
如果有两个这样的数组，
[i] 表示原数组 [0, i) 中的最大值
[i] 表示原数组(i,n)的最小值
内层循环可以通过[i] < nums[i] && nums[i] < [i] 来判断。
对于和两个数组，预先计算出来，即可得到各个数组。
递归如下：
总时间复杂度为
这个问题其实不难，但如果你在面试时第一次看到它并思考它，你很可能会非常紧张。
下面是 C++ 的参考实现和
参考代码 C++
#include
#include
#include
using namespace std;
vector<int> find(vector<int> nums) {
vector<int> res;
int n = nums.size();
vector<int> left_max(n, INT_MIN);
vector<int> right_min(n, INT_MAX);
for (int i = 1; i < n; i++) {
left_max[i] = max(left_max[i - 1], nums[i - 1]);
}
for (int i = n - 2; i >= 0; i--) {
right_min[i] = min(right_min[i + 1], nums[i + 1]);
}
for (int i = 0; i < n; i++) {
if (left_max[i] < nums[i] && nums[i] < right_min[i]) {
res.push_back(i);
}
}
return res;
}
int main()
{
vector<int> arr = {2,3,1,8,9,20,12};
auto res = find(arr);
for (int i = 0; i < res.size(); i++)
{
cout << res[i] << ' ';
}
}
def find(nums):
n = len(nums)
res = []
left_max = [float("-inf") for i in range(n)] # [0, i) 最大的值
right_min = [float("inf") for i in range(n)] # (i, n) 最小的值
for i in range(1, n):
left_max[i] = max(left_max[i-1], nums[i-1])
for i in range(n-2,-1,-1):
right_min[i] = min(right_min[i+1], nums[i+1])
for i in range(n):
if left_max[i] < nums[i] < right_min[i]:
res.append(i)
return res
print(find([2,3,1,8,9,20,12]))