c++ - 递增序列 C++

Question

我尝试在 CodeFights 上解决这个挑战，但没有成功。我最好的解决方案得到了 25/26(上次测试超过了时间限制)但我删除了它，因为我昨天试过了(它是 O(n^2))。现在我在 O(n) 中尝试了一个新的。我很累，我今天很想完成这个，所以请帮助我。

声明如下: 给定一个整数序列作为数组，确定是否可以通过从数组中删除不超过一个元素来获得严格递增的序列。

例子

For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

这是我到目前为止的代码...(糟糕的代码):

#include <iostream>
#include <vector>

#include <algorithm>

bool almostIncreasingSequence(std::vector<int> sequence) 
{
    int count = 0;


    for(int i = 0; i < sequence.size()-1; i++)
    {
        if(sequence[i] > sequence[i+1])
        {
            count++;
            sequence.erase(sequence.begin(), sequence.begin() + i);
            i--;
        }
        if(count == 2)
            return false;
    }
    return true;
}

int main()
{
    std::cout << std::endl;
    return 0;
}

Answer 1

这是一个运行时复杂度为 O(N) 的 C++11 解决方案:

constexpr auto Max = std::numeric_limits<std::size_t>::max();
bool is_sorted_but_skip(const std::vector<int>& vec, std::size_t index = Max){
    auto Start = index == 0 ? 1 : 0;
    auto prev = vec[Start];
    for(std::size_t i = Start + 1; i < vec.size(); i++){
        if(i == index) continue;
        if(prev >= vec[i]) return false;
        prev = vec[i];
    }
    return true;
}

bool almostIncreasingSequence(std::vector<int> v) 
{
    auto iter = std::adjacent_find(v.begin(), v.end(), [](int L, int R){ return L >= R; });
    if(is_sorted_but_skip(v, std::distance(v.begin(), iter)))
        return true;
    return is_sorted_but_skip(v, std::distance(v.begin(), std::next(iter)));
}

我们使用 std::adjacent_find查找第一个元素，iter 大于或等于它的下一个元素。然后我们在跳过 iter 的位置时检查序列是否严格排序。

否则，我们会在跳过 iter+1 的位置时检查序列是否严格排序

最坏情况复杂度:3 线性扫描

Demo