从左到右浏览数组并收集尽可能多的数字

让我详细解释一下我的思维过程，以便下次遇到相同类型的问题时，您会更容易。

首先，我在面对这类问题时经常犯的一个错误是模拟过程的冲动。问题陈述中提到的“模拟过程”是什么意思？该问题提到，进行一轮以最大化按特定顺序收集递增的数字。所以，你从 开始，找到它，看到下一个数字没有超出它，即，不能在同一轮中，并形成一个递增序列。所以，我们需要另一轮.现在我们发现，两者都可以在同一轮中收集，因为我们从左到右移动并按递增顺序取数字。但是我们不能接受，因为它开始于.最后，我们需要另一轮。总共有三轮。12212234245

现在，如果以这种方式模拟过程，问题就变得非常容易解决。在第一轮中，您查找形成从 开始的递增序列的数字。在开始第二轮之前，您可以删除这些数字。你继续这样，直到你用尽所有的数字。1

但是模拟这个过程将导致时间复杂度，无法通过问题陈述中提到的约束。因此，我们需要找到另一种方法，在不模拟整个过程的情况下提供相同的输出。

请注意，数字的位置在这里至关重要。为什么我们需要另一轮？因为它出现在.我们不需要另一轮，因为它在.同样，我们需要另一轮，因为它在 .213242

因此，在考虑每个数字时，我们只需要关注数字在顺序中的位置。在考虑时，我们看一下 ？是之前还是之后？之后，我们不需要另一轮。但如果它来得更早，我们将需要额外的一轮。对于每个数字，我们查看此条件，并在必要时递增整数。这样，我们就可以在不模拟整个过程的情况下计算出总轮数。2112

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector <int> v(n + 1), pos(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> v[i];
        pos[v[i]] = i;
    }
    int total_rounds = 1; // we'll always need at least one round because the input sequence will never be empty
    for(int i = 2; i <= n; ++i){
        if(pos[i] < pos[i - 1]) total_rounds++;
    }
    cout << total_rounds << '\n';
    return 0;
}

下次遇到此类问题时，请暂停一会儿，并尝试控制自己在代码中模拟流程的冲动。几乎可以肯定的是，会有一些聪明的观察结果，可以让你获得最佳解决方案。