相关疑难解决方法(0)

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

示例输入

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 …