有多个查询时，检查某些子数组是否已排序的有效方法是什么？

Question

假设一个数组A = {5, 4, 3, 7, 9, 11, 2}。有K很多查询。在每个查询中，我将得到两个整数L，R其中0 <= L <= R < N（N是数组的大小）。我必须告诉A[L...R]子数组是否已排序。

例如，第一个查询要求我告诉索引0到6（基于0的索引）的子数组是否已排序。答案是，A[0...6]没有排序。然后第二个查询问我是否A[2...5]排序。该子数组已排序。这是我的处理方法。有没有更好的办法？

int main()
{
    int a[7] = { 5, 4, 3, 7, 9, 11, 2}, k = 2;

    for(int i = 1; i <= k; i++)
    {
        int l, r;
        cin >> l >> r;
        bool isSorted = true;
        for(int j = l; j < r; j++)
        {
            if(a[j] > a[j + 1] )
            {
                isSorted = false;
                break;
            }
        }
        if(isSorted == true)
            cout << "Sorted" << endl;
        else
            cout << "Not Sorted" << endl;
    }
}

Answer 1

您可以对数据进行一次遍历，在每个索引处存储列表减少的最近的前一个索引。

然后，查询将包括从范围的右索引进行查找，并将结果值与范围的左索引进行比较。

int main(void)
{
    constexpr int a[7] = { 5, 4, 3, 7, 9, 11, 2};
    constexpr size_t k = 2;
    constexpr size_t N = sizeof a/sizeof a[0];
    size_t b[N];

    { /* preprocess */
        size_t last_decrease = 0;
        b[0] = 0;
        for( int x = 1; x < N; ++x )
        {
            if (a[x] < a[x-1]) last_decrease = x;
            b[x] = last_decrease;
        }
    }

    for(int i = 0; i < k; i++)
    {
        int l, r;
        std::cin >> l >> r;
        bool isSorted = l >= b[r];

        if (isSorted)
            std::cout << "Sorted\n";
        else
            std::cout << "Not Sorted\n";
    }
}

没有嵌套循环，因此此解决方案具有线性运行时。