前言
大家好，我是一个搬砖的胖子
这两天，一位同学给我发消息，
提到他在字节跳动-国际化电商三面中遇到的一道算法题。
这道题我搜了下，没在 Leetcode 找到。
因此，赶紧把这道原创题分享给大家。
其他的原创题都可以在 CodeTop 查看
题目描述
求数组中比左边元素都大同时比右边元素都小的元素，返回这些元素的索引
要求时间复杂度
输入：[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 ++) {
//右侧是否都比它大
}
//若两条件均满足则记录下来
}这种解法 ，不符合题目要求。
题目要求 ，外层循环肯定不能优化了，那有没有优化方法使内循环 呢？
有的！
通过分析可以得到，对于每个元素，如果它比左侧最大的值要大，同时比右侧最小的值要小，就满足条件。
那如果有这样两个数组，
left_max[i] 表示原数组 [0, i) 的最大值
right_min[i] 表示原数组 (i, n) 的最小值
内循环就可以通过 left_max[i] < nums[i] && nums[i] < right_min[i] 来判断了。
对于 left_max 和 right_min 这两数组，提前先算好，每个数组都能 得到。
left_max 和 right_min 递推式如下：
总时间复杂度为
参考代码
C++
Python
#include <iostream>
#include <vector>
#include <climits>
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] << ' ';
}
}评论 (38)
