其最小元素是特定給定數字的子陣列的數量

Question

給定一個數組，我想查找所有最小元素爲x的子陣列的數量。 其中x是一個給定的數字，可能存在或可能不存在於數組中，或者數組x中可能出現多次出現的數字。 O（n）實施將是優選的。

Answer 1

你有一個矢量vec已知的大小n。然後，對vec（i）的值與x的值進行比較。一旦找到一個高於x的值，該值可以是一組包含x作爲最小值的子向量的下界。你繼續超過元素運行VEC，並有兩種情況：

1）你發現一個元素比X較小，那麼這個下界不再有效了，你繼續搜索。

2）你發現X，讓您保存的相對位置對於下限，並繼續運行在指數直到找到一個值比X更小，讓你有上限。邊界包含一組子數組，其中x是最小值。計算所有可能的組合。

無論您是處於第1種情況還是第2種情況，您都會繼續運行索引，直到找到另一個有效範圍，或者直到達到向量的末尾。

int x; 
std::vector<int> vec(n); 
unsigned int l_bound = n; //initialize n to an invalid index 
unsigned int r_bound; 
unsigned int x_pos = n; //initialize x to an invalid index 
unsigned int n_sub_arrays = 0; 

// here we do something to assign values to vec and x 

// here we count the number of subarrays 
for (unsigned int i = 0; i<n; ++i) 
{ 
    if (vec(i) >= x) 
    { 
    if (l_bound == n) // if we are at the first value higher that x 
    { 
     l_bound = i; 
     if (vec(i) == x) // if this value is already x 
     { 
     x_pos = i; 
     } 
    } 
    } 
    else 
    { 
    if (x_pos == n) // x is not inside the bounds 
    { 
     l_bound = n; // the bounds are not valid   
    } 
    else 
    { 
     r_bound = i-1; 
     n_sub_arrays += (x_pos - l_bound+1)*(r_bound-x_pos+1); 
     l_bound = n; 
     x_pos = n; 
    } 
    } 
}