將數字分組在列表中

Question

我遇到了以下問題

給出了一個包含n個元素的數組A.這些元素現在被添加到一個新的列表L中，該列表最初是空的，並且基於給定的q查詢以特定的順序。

• 在每個查詢您將得到對應於甲的整數i [i]於陣列A.這意味着必須要添加的元素A [1]，將列表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。這樣您就不必對其進行排序，但之後您需要遍歷整個數組以按升序查找值。

方法1將是最好的，當q比Ñ少很多。方法2將更好地更大q。

使用這兩種方法，您將能夠按升序對所找到的值進行迭代，同時可以識別組及其值，還可以跟蹤最大的組值。只需要一次掃描即可找到答案。

Answer 2

讓我們先從兩個簡化的假設：

• 沒有重複。一旦給定索引i已被「查詢」，它將不會再被查詢。
• 無負數。所有元素都是正數或零，因此組中的最大值總是正數或零，因此擴展組（或合併兩組）不會導致整體「最大組值」減少。

（更下方，我會展示給不如何要求這些假設，但到目前爲止，這將簡化圖片。）

所以，每當我們「查詢」索引i，有四個案例：

• i-1目前是一組合適的端點（我指的是它的最大指數）和i+1目前是另一組的左終點。
  • 在這種情況下，我們需要將兩個羣組合併成一個羣組，其中i彌補了他們之間的差距。
• i-1當前是組的右端點，但i+1目前不在任何組中。
  • 在這種情況下，我們需要擴展組以覆蓋i。
• i-1當前未在任何一組，但i+1目前是一組的左終點。
  • 在這種情況下，與前面的情況一樣，我們需要擴展組以覆蓋i。
• i-1和i+1都不在組中。
  • 在這種情況下，我們有一個只有一個元素的新組。

在所有情況下，要注意關鍵的是，我們只在端點組感興趣。所以我們不需要從指數到它們的組的通用映射。 。 。這是很好的，因爲當我們合併兩個組時，那麼去更新每個索引從一個組指向另一個組是很昂貴的。

所以我們只需要三個映射：

std::unordered_map<int, int> map_from_left_endpoint_to_right_endpoint; 
std::unordered_map<int, int> map_from_right_endpoint_to_left_endpoint; 
std::unordered_map<int, int> map_from_left_endpoint_to_largest_value; 

爲了區分這四種情況，我們使用例如map_from_right_endpoint_to_left_endpoint.find(i - 1)（它返回指向組的左端點的迭代器，i-1是右端點（如果適用）;否則返回map_from_right_endpoint_to_left_endpoint.end()）。然後，我們刪除條目，因爲它們變得不再視爲適用（由於羣體正在擴大或合併在一個給定的方向），除（顯然）將新的條目，並更新現有項的值。

除了這些值，我們還需要一個

int maximum_group_value = 0; 

和每當我們延伸一組或合併兩個基團中，我們檢查所生成的組的值是否（意味着其largest_value * (right_endpoint - left_endpoint + 1）大於maximum_group_value 。如果是這樣，我們更新maximum_group_value並返回;如果不是，我們按原樣返回maximum_group_value。

---

現在，如果重複被允許的，從而給定指標i可能被「詢問」它已經屬於後一組？

最簡單的方法是簡單地跟蹤哪些i -s已經被查詢;但一個更優雅的方式，如果需要的話，可能會改變從std::unordered_mapmap_from_left_endpoint_to_right_endpoint到std::map，然後用這樣的：

bool is_already_in_a_group(
    std::map<int, int> const & map_from_left_endpoint_to_right_endpoint, 
    int const i) { 
    // get iterator to first element *after* index (or to 'end()' if no such): 
    auto iter = map_from_left_endpoint_to_right_endpoint.upper_bound(index); 
    // if that pointer points to 'begin()', then there are no elements 
    // at or before index: 
    if (iter == map_from_left_endpoint_to_right_endpoint.begin()) { 
    return false; 
    } 
    // otherwise, move iterator to point to the last element whose key is 
    // less than or equal to index: 
    --iter; 
    // . . . and check whether the value of that element is greater than 
    // or equal to index (meaning that [key, value] spans index): 
    return iter->second >= index; 
} 

檢查的最大關鍵在map_from_left_endpoint_to_right_endpoint小於或等於i被映射到大於或等於i的值。

這增加了五分之一的情況下，以我們的情況分析，上述—「如果i已經是一個組裏面，只要什麼都不做，返回maximum_group_value」 —但除此之外，沒有任何效果。

注意，同樣的方法也可以讓我們消除map_from_right_endpoint_to_left_endpoint，如果我們想：上述功能可以很容易地通過改變其return聲明return iter->second == index ? iter->first : -1;進行調整，以int get_left_endpoint_for_right_endpoint。

在這一點上變得合理界定一個Group類三個字段（left_endpoint，right_endpoint和largest_value），並只保留一個map_from_left_endpoint_to_group。

---

最後—如果負值允許什麼，這樣的「最大羣體價值」，實際上下降作爲查詢的結果呢？ （例如，如果數組元素是[-1, -10]而查詢是i=0，i=1，那麼結果是maximum_group_value=-1,maximum_group_value=-2）。在這種情況下，我們需要跟蹤所有當前組的值，因爲它們中的任何一個可能突然成爲最大值。

對於這一點，而不是存儲在單個int maximum_group_value，我們可以保持羣體的堆，通過值排序，我們推到每一個我們創建/擴展/合併組時間。 （我們可以只使用一個std::vector<Group>這一點，再加上std::push_heap用適當的比較，或者用適當的定義operator<(Group const &, Group const &)。）每次查詢後，我們檢查，如果在堆（向量中的第一個元素）頂部集團仍然是一個實際存在的團體;如果是這樣，我們返回其值，否則我們彈出它（使用std::pop_heap）和重複。

作爲一種優化，我們可以也店int maximum_group_value，消除堆一旦我們遇到了一個非負的數組元素（因爲一旦給定組包含一個非負的數組元素，它的值不能減少再次，顯然最大的羣體價值將是這些羣體之一的價值）。