面试 - 在阵列中查找幅度极点

Question

幅度极点:数组中的元素,其左侧元素小于或等于它,右侧元素大于或等于它.

示例输入

3,1,4,5,9,7,6,11

期望的输出

4,5,11

我在面试中被问到这个问题,我必须返回元素的索引,并且只返回满足条件的第一个元素.

我的逻辑

1. 取两个MultiSet(这样我们也可以考虑复制),一个用于元素的右侧,一个用于元素的左侧(极点).
2. 从第0个元素开始,将所有元素放在"右边的集合"中.
3. 如果第0个元素小于或等于"right set"上的所有元素,则返回其索引.
4. 否则将其放入"左集"并从索引1处的元素开始.
5. 遍历数组,每次从"左设置"中选择最大值,从"右设置"中选择最小值并进行比较.
6. 在任何元素的任何时刻,其左边的所有值都在"左集"中,右边的值在"右集"中

码

int magnitudePole (const vector<int> &A) {  
   multiset<int> left, right;        
   int left_max, right_min;          
   int size = A.size();
   for (int i = 1; i < size; ++i)
       right.insert(A[i]);
   right_min = *(right.begin()); 
   if(A[0] <= right_min)
       return 0;
   left.insert(A[0]);
   for (int i = 1; i < size; ++i) {
       right.erase(right.find(A[i]));
       left_max = *(--left.end());
       if (right.size() > 0)
           right_min = *(right.begin());
       if (A[i] > left_max && A[i] <= right_min)
           return i;
       else
           left.insert(A[i]);
   }
   return -1;
}

我的问题

• 我被告知我的逻辑是不正确的,我无法理解为什么这个逻辑是不正确的(虽然我检查了一些情况并且它正在返回正确的索引)
• 为了我自己的好奇心如何在O(n)时间内不使用任何set/multiset这样做.

Answer 1

对于O(n)算法:

1. 对于[0,length(n))中的所有k,计算从n [0]到n [k]的最大元素,将答案保存在数组maxOnTheLeft中.这花费O(n);
2. 对于[0,length(n))中的所有k,计算从n [k]到n [length(n)-1]的最小元素,将答案保存在数组minOnTheRight中.这花费O(n);
3. 遍历整个事物并找到任何n [k]与maxOnTheLeft <= n [k] <= minOnTheRight.这花费O(n).

你的代码在这里是错误的(至少)错误:

if (A[i] > left_max && A[i] <= right_min) // <-- should be >= and <=