用于成对比较和跟踪 max/longest 序列的 STL 算法

Question

考虑这个相当简单的算法问题：

Given an array of (unsorted) numbers, find the length of the longest sequence of adjacent numbers that are increasing. For example, if we have {1,4,2,3,5}, we expect the result to be 3 since {2,3,5} gives the longest increasing sequence of adjacent/contiguous elements. Note that for non-empty arrays, such as {4,3,2,1}, the minimum result will be 1.

这个有效：

#include <algorithm>
#include <iostream>
#include <vector>

template <typename T, typename S>
T max_adjacent_length(const std::vector<S> &nums) {
  if (nums.size() == 0) {
    return 0;
  }
  T maxLength = 1;
  T currLength = 1;

  for (size_t i = 0; i < nums.size() - 1; i++) {
    if (nums[i + 1] > nums[i]) {
      currLength++;
    } else {
      currLength = 1;
    }
    maxLength = std::max(maxLength, currLength);
  }
  return maxLength;
}

int main() {
  std::vector<double> nums = {1.2, 4.5, 3.1, 2.7, 5.3};
  std::vector<int> ints = {4, 3, 2, 1};
  std::cout << max_adjacent_length<int, double>(nums) << "\n"; // 2
  std::cout << max_adjacent_length<int, int>(ints) << "\n"; // 1
  return 0;
}

作为我自己的练习，我想知道是否有 is/are STL 算法可以达到相同的效果，从而（理想情况下）避免我拥有的原始 for 循环。这样做的动机是为了更多地了解STL算法，并练习使用抽象算法使我的代码更通用和可重用。

这是我的想法，但它们完全实现了我想要的。

std::adjacent_find 实现了成对比较，可用于查找非递增对的索引，但不容易促进保持当前和最大长度并比较两者的能力。可以将这些状态变量作为我的谓词函数的一部分，但这似乎有点不对，因为理想情况下您希望您的谓词函数没有任何副作用，对吗？
std::adjacent_difference 很有趣。人们可以用它来构造相邻数字之间的差异向量。然后，从第二个元素开始，根据差异是正数还是负数，我们可以再次追踪看到的连续正数差异的最大数量。这实际上非常接近实现我们想要的。请参阅下面的示例代码：
```
#include <numeric>
#include <vector>

template <typename T, typename S> T max_adjacent_length(std::vector<S> &nums) {
  if (nums.size() == 0) {
    return 0;
  }
  std::adjacent_difference(nums.begin(), nums.end(), nums.begin());
  nums.erase(std::begin(nums)); // keep only differences
  T maxLength = 1, currLength = 1;
  for (auto n : nums) {
    currLength = n > 0 ? (currLength + 1) : 1;
    maxLength = std::max(maxLength, currLength);
  }
  return maxLength;
}
```
这里的问题是，如果我们想计算差异，我们会失去 nums 的常量性，或者我们必须牺牲 space 并创建 nums 的副本，这是一个否-否，因为原始解决方案已经是 O(1) space 复杂度。

有没有我忽略的 idea/solution 以简洁易读的方式实现我想要的东西？

Answer 1

在您的两个代码片段中，您都在遍历一个范围（在第一个版本中，使用 index-based-loop，在第二个版本中使用 range-for 循环）。如果你想使用标准算法，这不是你真正应该编写的代码，它与范围内的迭代器一起工作。如果您开始考虑成对的迭代器，而不是将范围视为元素的集合，那么选择正确的算法会变得更容易。

对于这个问题，下面是一个合理的代码写法：

auto max_adjacent_length = [](auto const & v)
{
    long max = 0;
    
    auto begin = v.begin();
    
    while (begin != v.end()) {
        auto next = std::is_sorted_until(begin, v.end());
        max = std::max(std::distance(begin, next), max);
        begin = next;              
    }
    
    return max;
};

这是一个demo。

请注意，您在选择合理算法方面已经走在了正确的轨道上。这也可以用 adjacent_find 解决，只需多做一点工作。

用于成对比较和跟踪 max/longest 序列的 STL 算法

STL algorithms for pairwise comparison and tracking max/longest sequence

c++

algorithm

stl