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

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

输入示例

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

期望的输出

4,5,11

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

My logic

1. 取两个 MultiSet（这样我们也可以考虑重复），一个用于元素的右侧，一个用于元素的左侧 元素（极）。
2. 从第 0 个元素开始，并将其余所有元素放入“正确的集合”中。
3. 基本条件如果第 0 个元素小于或等于“右集”上的所有元素，则返回其索引。
4. 否则将其放入“左集”并从索引 1 处的元素开始。
5. 遍历数组，每次从“左组”中选取最大值，从“右组”中选取最小值并进行比较。
6. 在任何时刻，对于任何元素，其左侧的所有值都在“左集”中，其右侧的值都在“右集”中

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

我的问题

• 我被告知我的逻辑不正确，我无法理解为什么这个逻辑不正确（尽管我已经检查了一些情况并且 它返回正确的索引）
• 出于我自己的好奇心，如何在 O(n) 时间内不使用任何集合/多重集来做到这一点。

对于 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

你的代码（至少）在这里是错误的：

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