Ловлю переполнение на лите

Рейтинг: -1Ответов: 1Опубликовано: 16.04.2023

https://leetcode.com/problems/max-consecutive-ones/

class Solution {
public:
        int findMaxConsecutiveOnes(vector<int>& v) {
                vector<int> counter;
                int result = 0;
                for(int i = 0; i < v.size(); i++) {
                        int unit_counter = 0;
                        while(v[i] != 0 && i < v.size()) {
                                unit_counter++;
                                i++;
                        }
                        counter.push_back(unit_counter);
                }
                sort(counter.rbegin(), counter.rend());
                result = counter[0];
                return result;
        }
};

Попалась такая задачка на лите. Код проходит все локальные тесты, но лит почему-то ругается на переполнение кучи. Делал свой тест с такими же значениями - всё ок. С чем может быть связана проблема?

c# алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Смотрим сюда:

while(v[i] != 0 && i < v.size()) {
    unit_counter++;
    i++;
}

Что будет при i = v.size()-1? Выполнение тела цикла, после чего i становится равным v.size(), после чего выполняется проверка v[i] != 0, для чего выполняется обращение куда? Правильно, за рамки вектора...

Но вообще-то какой-то у вас подход не очень эффективный... Вот так не проще, быстрее и меньше памяти надо?

int findMaxConsecutiveOnes(vector<int>& v)
{
    int max = 0, last = 0, cur = 0;
    for(int i = 0; i < v.size(); i++)
    {
        if (v[i] == 1)
        {
            if (last == 0) { last = 1; cur = 1; }
            else cur++;
        }
        else
        {
            last = 0;
            if (cur > max) max = cur;
        }
    }

    if (cur > max) max = cur;

    return max;
}