对于一个O（n）的算法：

1. 计数在[0从n个[0]对于所有的k的最大元素到n [k]的，长度（n））的，保存在一个数组maxOnTheLeft答案。此费用为O（n）;
2. 计数从n个[k]的最小的元素到n [长度（正）-1]为在所有的k [0，长度（n））的，保存在一个数组minOnTheRight答案。此费用为O（n）;
3. 遍历整个事情，并找到maxOnTheLeft＆LT任意n [K] = N [K]＆LT; = minOnTheRight。此费用为O（n）。

和你code是（至少）错在这里：

 如果（A [I]＆GT; left_max和放大器;＆放大器; A [1]  -  = right_min）//＆LT;  - 应该是＆GT; =和＆lt; =
 

Magnitude Pole: An element in an array whose left hand side elements are lesser than or equal to it and whose right hand side element are greater than or equal to it.

example input

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

desired output

5,11

I was asked this question in an interview and I have to return the index of the element and only return the first element that met the condition.

My logic

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"

Code

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

My questions

• 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.

For an O(n) algorithm:

1. Count the largest element from n[0] to n[k] for all k in [0, length(n)), save the answer in an array maxOnTheLeft. This costs O(n);
2. Count the smallest element from n[k] to n[length(n)-1] for all k in [0, length(n)), save the answer in an array minOnTheRight. This costs O(n);
3. Loop through the whole thing and find any n[k] with maxOnTheLeft <= n[k] <= minOnTheRight. This costs O(n).

And you code is (at least) wrong here:

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