Кратчайший несортированный непрерывный подмассив

Интуиция

Поскольку только часть массива не отсортирована, скажем, part[lo: hi] не отсортирована
и [0:lo] и [hi:n] отсортированы, поэтому нам нужно найти хуки, которые будут привет, привет. Здесь приходит идея двух указателей.

Подход

Сначала найдите «lo» справа налево, где начинается наше первое возмущение. На этом "привет" заканчивается.

Для lo-: запустить цикл от 0 до n-1.if(nums[i]›nums[i+1])наш lo становится i и прерывается; Экс- 1,4,2,5 . Тогда lo будет индексом 1. For hi-: запустить цикл от n-1 до 1.if(nums[i-1]›nums[i])

наше привет становится «и» и ломается;

Экс- 1,4,2,5,3. Тогда привет - это индекс 4.

Теперь в диапазоне lo:hi (включая оба) нам нужно найти максимальное и минимальное значения.

Пример-1,4,2,0,5,3 lo:1, hi:3, теперь, если мы напрямую отсортируем от lo до hi, то 0 не будет помещен в правильный индекс -›(1,0,2,3,5,4).

Итак, нам нужно найти максимальное и минимальное значения.
Затем найдите их фактическое правильное место в массиве и сохраните их в lo, hi соответственно.

Наконец верните hi-lo+1.

Сложность

  • Временная сложность:O(n)
  • Сложность пространства:O(1)

Код

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int lo=-1,hi=-1;
        int n=nums.size();
        for(int i=0;i<n-1;i++)
        {
            if(nums[i]>nums[i+1])
            {
                lo=i;
                break;
            }
        }
        for(int i=n-1;i>=1;i--)
        {
            if(nums[i-1]>nums[i])
            {
                hi=i;
                break;
            }
        }
        cout<<"lo="<<lo<<" hi="<<hi<<"\n";

        if(lo==-1 and hi==-1)
        return 0;
        int mini=nums[lo],maxi=nums[hi];
        for(int i=lo;i<=hi;i++)//Finding minimum and maximum in the range lo->hi
        {
            mini=min(mini,nums[i]);
            maxi=max(maxi,nums[i]);
        }
        cout<<"mini="<<mini<<" "<<"maxi="<<maxi;
        for(int i=0;i<n;i++)//Finding correct place of minimum value
        {
            if(nums[i]>mini)
            {
                lo=i;
                break;
            }
        }
        for(int i=n-1;i>=0;i--)//Finding correct place of maximum value
        {
            if(nums[i]<maxi)
            {
                hi=i;
                break;
            }
        }
        return hi-lo+1;
    }
};

  PLEASE APPLAUD IF FOUND USEFUL.