c++ - 所有 k 个子序列的最小值中的最大值

Question

你有一个包含 n 个元素的序列。从 k 个元素的连续子序列中找出所有最小值中的最大值。我尝试了采用所有长度为 k 的序列的经典方法。然后取最小值。并找到新的最小值数组的最大值。

一个更优的解决方案是找到前 k 个元素的最小值，然后在它之后跳转。并且您跳过了一些迭代。

你能给我一个更好的最优解决方案吗？没关系，但我正在使用 C++。

Answer 1

好吧，虽然这可能是一项任务，但我希望您对执行这些操作有一种通用且简洁的 STL 风格的感觉。

template<typename Iter, typename T = typename std::iterator_traits<Iter>::value_type>
std::pair<T, T> KConsecutiveMinMax(Iter first, Iter last, std::size_t K){
    if(std::distance(first, last) < K) return {};

    auto Sum = std::accumulate(first, first+K, T());
    auto Min = Sum;
    auto Max = Sum;
    for(auto left = first, right = first + K; right != last; Sum -= *left++, Sum += *right++)
        std::tie(Min, Max) = std::minmax(std::min(Min, Sum), std::max(Max, Sum));
    return {Min, Max};
}

它添加数组的前 K 个元素，将它们分配给 Sum、Max 和 Min，然后在减去尾部元素的同时添加第 K+1 个元素。对于其中的每一个，它提取新局部子序列总和的新 Min 和 Max

例子:

int main(){
    std::vector<int> v{2, 39, 1, 9, 8, 6, 3, 10, -42, 3, 8, 3, 2};
    auto ans = KConsecutiveMinMax(v.begin(), v.end(), 3);
    std::cout << "Min = " << ans.first << ", and Max = " << ans.second << std::endl;
}

输出:

Min = -31, and Max = 49

Demo