algorithm - 面试 - 在数组中查找幅度极点

Question

极点:数组中左侧元素小于或等于它且右侧元素大于或等于它的元素。

示例输入

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

期望的输出

4,5,11

面试时被问到这个问题，要返回元素的索引，只返回第一个满足条件的元素。

我的逻辑

1. Take two MultiSet (So that we can consider duplicate as well), one for right hand side of the element and one for left hand side of the element(the pole).
2. Start with 0th element and put rest all elements in the "right set".
3. Base condition if this 0th element is lesser or equal to all element on "right set" then return its index.
4. Else put this into "left set" and start with element at index 1.
5. Traverse the Array and each time pick the maximum value from "left set" and minimum value from "right set" and compare.
6. At any instant of time for any element all the value to its left are in the "left set" and value to its right are in the "right set"

代码

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;
}

我的问题

• I was told that my logic is incorrect, I am not able to understand why this logic is incorrect (though I have checked for some cases and it is returning right index)
• For my own curiosity how to do this without using any set/multiset in O(n) time.

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. 遍历整个过程并找到 maxOnTheLeft <= n[k] <= minOnTheRight 的任何 n[k]。这花费了 O(n)。

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

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