algorithm - 对列表中的数字进行分组

Question

我遇到了以下问题，

给定一个包含 n 个元素的数组 A。这些元素现在被添加到一个新的列表 L 中，该列表最初是空的，根据给定的 q 查询以特定的顺序。

• 在每个查询中，您都会得到一个整数 i，它对应于数组 A 中的 A[i]。这意味着您必须将元素 A[i] 添加到列表 L。
• 将每个元素添加到列表L后，将列表L中的元素分组。如果两个元素在数组A中的索引连续，则它们在同一组中。
• 对于每个组，我们将组的值定义为 axb，其中 a 是该组中的最大值，b 是该组的大小。

打印每个元素添加到列表L后形成的所有组中的最大组值。

我的方法是使用 map<int,vector<int>>其中键是组号，值是包含组大小最大值的向量。组。我还有一个数组 g 和 g[i] 表示 a[i] 的组号，-1 如果它不在任何组中。下面的代码是我实现的一部分，但我确信有更好的方法来解决这个问题，因为我的这个解决方案在某些情况下给出了 TLE 和 WA，而且我似乎无法找出正确的方法。请提出解决此问题的最佳方法。

int g[a.size()+2];       //+2 because queries start with index 1, and g[i] corresponds to a[i-1] 
for(int i=0;i<a.size()+2;i++)
    g[i]=-1;
int gno=1;
map<int,vector<int> > m;
vector<int> ans;
int mx=0;
for(unsigned int i=0;i<queries.size();i++){
    int q = queries[i];
    if(g[q-1]==-1 && g[q+1]==-1){
      //create new group with current eleent as first element
        g[q] = gno;        //gno is the group number.
        vector<int> v;

        v.push_back(1);
        v.push_back(a[q-1]);
        m[gno]=v;
        mx = max(mx,m[gno][0]*m[gno][1]);
        gno++;
    }
    else if(g[q-1]!=-1 && g[q+1]==-1){
      //join current element to left group
        g[q] = g[q-1];
        m[g[q]][0]++;
        m[g[q]][1] = max(m[g[q]][1],a[q-1]);
        mx = max(mx,m[g[q]][0]*m[g[q]][1]);
    }
    else if(g[q-1]==-1 && g[q+1]!=-1){
      //join current element to right group
        g[q] = g[q+1];
        m[g[q]][0]++;
        m[g[q]][1] = max(m[g[q]][1],a[q-1]);
        mx = max(mx,m[g[q]][0]*m[g[q]][1]);
    }
    else{
       //join both groups to left and right
        g[q]=g[q-1];
        int g1 = g[q];
        int i;
        m[g[q]][0] += 1 + m[g[q+1]][0];
        m[g[q]][1] = max(m[g[q]][1],max(a[q-1],m[g[q+1]][1]));
        for(i=q+1;g[i]==g[i+1];i++){
            g[i]=g1;
        }
        g[i]=g1;
        mx = max(mx,m[g[q]][0]*m[g[q]][1]);
    }
    ans.push_back(mx);
}

.

Answer 1

我实际上不会构建列表 L。查找如何处理新值可能会花费太多时间:它本身是一个新组吗，它是否扩展了现有组，两个组是否需要合并到一？如果第一个值相距很远，您将有很多组，并且您需要用每个新的传入值迭代它们:这效率不高。

我会先收集所有的值，然后再看看它们如何适合分组。

有两种方式收集值:

1. 将它们存储在一个列表中，当收集到所有值后，将列表按升序排序

2. 标记大小为 n 的 bool 数组中的条目。这样您就不必对其进行排序，但之后您确实需要迭代整个数组以按升序查找值。

当 q 远小于 n 时，方法 1 是最佳选择。对于更大的 q，方法 2 会更好。

使用这两种方法，您都可以按升序迭代找到的值，同时您可以识别组、它们的值，并跟踪最大的组值。只需扫一扫即可找到答案。