时间戳

首页 > 解决方案 > 如何在复杂度 O(n) 中解决单调数组问题？

c++ - 如何在复杂度 O(n) 中解决单调数组问题？

问题描述

一个数组是单调的，如果它是递增的或单调递减的。

例子：

输入：[1,2,2,3] 输出：真

输入：[3,2,2,1] 输出：真

输入：[1,3,2] 输出：假

这是我的 O(nlogn) 时间复杂度的代码。我使用排序和一个额外的数组来解决这个问题。我的代码如下：

    bool isMonotonic(vector<int> array) {


    vector<int>extraArray;
    int i,j;
    for(i=0;i<array.size();i++){
        extraArray.push_back(array[i]);
    }
    
    sort(extraArray.begin(),extraArray.end());
    
    for(i=0;i<array.size();i++){
        if(array[i] != extraArray[i])
            break;
    }
    if(i == array.size())
        return true;
    
    for(i = array.size() -1,j=0;j<extraArray.size();i--,j++){
        if(array[i] != extraArray[j])
            break;
    }
    if(j == extraArray.size())
        return true;
    
  return false;
}

如何以 O(n) 时间复杂度解决它？

标签： c++algorithmtime-complexity

解决方案

您使用的策略通过将数组排序为子步骤来工作。使用标准排序算法需要时间 O(n log n)，这是代码中的瓶颈。问题是——你真的需要对数组进行排序来做到这一点吗？

作为提示，请查看前两个元素。如果第二个元素大于第一个元素，那么数组单调的唯一方法是整个数组单调递增。你能检查一下是不是这样吗？如果第二个元素小于第一个元素，则数组单调的唯一方法是整个数组单调递减。你能检查一下吗？如果前两个元素相等，你应该怎么做？

推荐阅读