Առավելագույն իրար հաջորդող Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon
Դասավորություն

Խնդիրի հայտարարություն

Max իրար հաջորդող խնդրում տրված է երկուական զանգված: Պետք է գտնել տվյալ զանգվածում առկա անընդմեջների առավելագույն քանակը:
Մուտքային զանգվածը պարունակում է միայն 0 և 1:

Օրինակ

[1,1,0,1,1,1]
3

Բացատրությունը.
Առաջին երկու թվանշանները կամ վերջին երեք նիշերը հաջորդական 1-երն են:
Հաջորդ 1-ների առավելագույն քանակը 3 է:

[0,1,0]
1

Բացատրությունը.
Հաջորդ 1-ների առավելագույն քանակը 1 է:

Մոտեցում

Այս խնդիրը լուծելու համար մենք կարող ենք կրկնել զանգվածի ինդեքսների միջոցով երկու անգամ nested while հանգույց հետևյալ ալգորիթմով.

1. Ստեղծեք փոփոխական առավելագույն, որը կպահպանի թարմացված առավելագույն հաջորդական 1-երը տրավերսման ընթացքում:
2. Ստեղծել և նախաստորագրել i ինդեքսը `առաջին ցուցիչով:
3. Այժմ գործարկեք մի քանի հանգույց մինչև i <զանգվածի չափը:
4. Օղակի ներսում մենք ստուգելու ենք, արդյոք ընթացիկ ինդեքսում համարը 1 է 1, թե ոչ: Եթե ​​այն հավասար չէ 1-ի, ապա պարզապես ավելացրեք i ինդեքսը: Այլապես, եթե դա հավասար է 0-ի, ապա գործարկիր ներդիրներով մի օղակը `ստեղծելով հաշվարկի փոփոխական և նախաստորագրիր 1.-ով: Ապա անցիր զանգվածը հաջորդական 1-երի համար այդ ներդիրավորված հանգույցում: այսինքն `անցումային զանգվածը, մինչդեռ num [i] - ը հավասար է 1-ի, ինչպես նաև շարունակաբար ավելացնել ընթացիկ անընդմեջ XNUMX-ների քանակը, ինչպես ցույց է տրված ստորև նկարում:

Մաքսային անընդմեջները
5. rayանգվածի 0-ի կամ վերջի հետ բախվելուց հետո թարմացրեք առավելագույն փոփոխականը `համեմատելով դրա հին արժեքը հաշվարկի փոփոխականում պահվող 1-ական անընդմեջ հաշվարկի հետ:
6. Մինչ հանգույցն ավարտվում է, վերադարձեք առավելագույն արժեքը:

Իրականացման

C ++ ծրագիր առավելագույնը իրար հաջորդող Leetcode լուծման համար

#include <bits/stdc++.h>
using namespace std;

int findMaxConsecutiveOnes(vector<int>& nums) {

    int maximum=0;
    int i=0;

    while(i<nums.size())
    {
        int conOnes=0;
        while(i< nums.size() && nums[i]==1)
        {
            conOnes++;
            i++;
        }

        maximum=max(maximum,conOnes);
        i++;
    }

    return maximum; 
}

int main() 
{
    vector<int> nums={1,1,0,1,1,1};
    cout<<findMaxConsecutiveOnes(nums)<<endl;

  return 0; 
}
3

Java ծրագիր առավելագույն հաջորդականների համար Leetcode լուծման համար

import java.lang.*;

class MaxOnes
{  
    public static int findMaxConsecutiveOnes(int[] nums) 
    {
        int maximum=0;
        int i=0;

        while(i<nums.length)
        {
        int conOnes=0;
        while(i< nums.length && nums[i]==1)
        {
        conOnes++;
        i++;
        }

        maximum=Math.max(maximum,conOnes);

        i++;
        }

        return maximum; 

    }
    
    public static void main(String args[])
    {
        int nums[]={1,1,0,1,1,1};

        System.out.println(findMaxConsecutiveOnes(nums));
        
    }
}
3

Բարդության վերլուծություն առավելագույն հաջորդականների համար Leetcode լուծման համար

Timeամանակի բարդություն

ՎՐԱ) : Մենք անցնում ենք զանգվածը սկսած ինդեքսից մինչև վերջին ինդեքս և այցելում յուրաքանչյուր ինդեքս միայն մեկ անգամ: Հետևաբար, ժամանակի բարդությունը կլինի գծային O (N):

Տիեզերական բարդություն 

O (1): Մենք ոչ մի լրացուցիչ տարածք չենք օգտագործում, ուստի օգտագործվող տարածքը կայուն է: