Есть массив чисел. Каждое число - это высота дома, например:
https://i.imgur.com/OOwGCLS.png
Это для массива 5 1 3 0 4.
Пошёл дождь и пространство между домами заполнилось водой. Нужно посчитать объём воды, которая скопилась между домами.

Вот так вода заполнит исходный пример:
https://i.imgur.com/fOXWNTH.png

Можно без нахождения максимума сделать цикл в цикле пока они не встретятся, чутка дешевле выйдет, только надо определять переменную которая показывает какая сторона выше на данной итерации

(85) красиво

(92) Но два прохода

(85) Прикольно, да
Можно, кстати, даже в один цикл сделать :))

(93) два не полных прохода, это в счёт?

(85) по-твоему там только две лужи воды образуется? это не так

(95) Почему неполных - максимум чтоб найти это один проход, далее с двух сторон накопить пустоту - вот и второй проход

(97) упс) а если (91) ?

(98) Цикл в цикле - это больше двух

(88) с++
(89) Да ладно, все понятно же
Код сложнее читать

(90) На js не проще такие поделки писать?) Я codepen.io пользую
(92) Я тоже порадовался, что еще что-то могу)

(93) O(N). Остальное не важно)
(94) Как?

(96) Не понял вопроса.
(98) Похоже на изврат) Но давай код :)

(99) ну так количества итераций не будет больше количества элементов

(54) а если..., все написано в (30) и смотри (90)

(100) А, не, не получается

(100) или я не понял решения в (85) или из него следует, что считается объем двух резервуаров только - до максимума и после

(104) Аналогично

(87) Вроде правильно считает.

Только зачем СписокЗначений, когда есть массив?

(104) Не понял

Так (85) походу работает, только если максимум один, так?

(106) Как ты сделаешь реквизит формы типа Массив?

(108) Нет

(108) поэтому нужно определить идентификатор максимума, а не значение

(102) Какая сложность получается в (90)?

(104)(105) Ну так по сути самый большой дом разбивает все дома на два резервуара.

(108) Не, их может быть несколько. Главное чтобы слева и справа шли к одному и тому же.

Ну и вот для наглядности мб кому пригодится:
https://i.imgur.com/IrkfjRV.png

(100) Блин, код получается суперговнокодом, типа
"если левыйбольше тогда правый = массив[правыйитератор] иначе
Левый = массив[левыйитератор]"
Не получается сейчас думать, но общая идея такая
Находим этажи слева, в том же коде находим этажи справа, сравниваем какой больше и идём с меньшего к большему попутно считая сколько воды заполняем, если представить визуально - поднятие линейки вверх с отметкой заполненности

112) резрвуаров может и пять получиться в итоге

"их может быть несколько. Главное чтобы слева и справа шли к одному и тому же" // А к какому идти тогда, если их несколько одинаковых, к любому?

(114) Max - это L из (85)
https://i.imgur.com/aSe7nTq.png

(115) Да, к любому

(115) (111)

(115) Вот для двух:
https://i.imgur.com/rUAhwWx.png

(116) А чем тогда M и L отличаются?

(112) в (90) сложность O(N)

А, L это локальный максимум текущего шага, изначально равен высоте дома первого шага

(112) Эээ, нихрена не на два
3 0 3 0 5 0 3 0 3
Сколько резервуаров?
https://yadi.sk/i/mTv1DEDdHsjeIg

(122) два с одинаковой высотой разделенные максимумом с высотой 5

(123) Че?

+(124) Так-то вроде 4, я даже раскрасил же

(122) ну, суть в том, что расчета фактически происходит два - слева и справа, а не в том, что там фактически 4 резервуара)
одумайте мысль в (113) плз

(122) Это уже терминология, что называть "резервуаром". По факту в (85) корректное решение и единственное подходящее под ограничения (55).
Пусть будет две "области"

Додумайте* (126)

(122) вот и я также думаю
я вообще могу этих луж нарисовать, они все будут умньшаться по уровню от максимума влево и вправо
https://cdn1.radikalno.ru/uploads/2020/5/26/fd20b06a3b533fd96b638e94719522e3-full.png

(126) Слова резервуар и расчет для тебя синонимы?

(127) да, две "области" самая верная терминология)

(120) Не похоже.
Берем [5,4,3,2,1] (большую убывающую лесенку)

Далее:
Выбираем самый левый дом за базовый.
Ищем следующий базовый от текущего базового как:
- первый слева направо, выше текущего
- если таковых нет: то крайний справа из тех, что с максимальной высотой

На втором пункте много побегать придется, не?

(130)(129) Вы о разном. Сначала PR не понял (104) в (107), а теперь топит за (104) :)

Касательно (104), глянь 116. Должно стать понятнее)

(129) Не важно сколько луж/дыр/резервуаров. Важно, что проход от краев к одному из максимумов позволяет избавиться от необходимости использовать допмассивы

(130) может не будем углубляться, это не относится к теме, тут ошибочка вышла, верно

(127) категорически не согласен
во-первых резервуаров с разными уровнями может быть больше, см рисунок (129)
во-вторых мое решение в (90) вполне O(n) и с доп памятью O(1)

(135) вложенный цикл, не может там быть O(N)

(129) Да блин, не тупи, в (85) все верно, просто он скудно описал мысль
Ищешь номер максимально высокого дома (любого, если их несколько)
Потом слева и справа идешь к этому максимуму с шагом один дом и смотришь, сколько воды умещается между текущим домом и следующим
При этом в расчете берешь высоту дома, максимальную в твоем проходе (отдельно для левого, отдельно для правого)

(136) а ты так определяешь? а что итератор внешнего цикла двигается только внутренним ничего не говорит?

(137) а потом запоминаем следующий максимальный и т.д., этого в (85) не было написано

(132) Гражданин, о чем вы?
В (107) я сказал, что Ненавижу 1С в (104) не понял

(135) Слушай, не гунди, в (85), похоже, оптимальный вариант :))

(139) Как не было?
Вот же:
>Идем слева, запоминая высоту самого высокого дома - L

читать как "запоминая высоту самого высокого встретившегося дома"

(135) Ты на (132) не ответил.

(139) Я же и говорю, скудно написал, с предполагаемыми домысливаниями

(143) тогда я и в (30) написал решение )))
(142) на что я не ответил?

(138) Это просто "извращение" с учетом возврата ( var nextBased = based;...based = nextBased;) по сути это обычный вложенный цикл и сложность скорее всего О(N^2), как бы хитро ты его не обходил :). 100% выше O(N)

(144) То, что ты в (30) написал, даже с поллитрой никто не разберет, особенно последнее "А потом просто решаем задачу"

Так, в одну итерацию кто-нибудь придумал?
Вот так получается (113) ?

Ладно, убедили, еще подумаю

(146) нет там таких слов, ну посчитать объем всегда можно

Смотрите, какой я молодец, переписал (90) на js :)
https://codepen.io/DTX/pen/rNOgOqN?editors=1011

И даже подсчет итераций сделал :)

"Elems: 40. Iterations: 780"
"Elems: 80. Iterations: 3160"
Не тянет на О(N)

(150) растёт быстрее чем О(N), так что ...

(150) О(N^2) как и предполагалось в (145). Запусти ещё пару раз для пущей убедительности)

(152) Так там же (150) прям в браузере можно код менять, он сразу и выполнится) Удобно, попробуйте
Не понимаю, как кто-то тут на 1С прогают такие вещи)

0 "Elems: 1000. Iterations: 499500"
0 "Elems: 2000. Iterations: 1999000"
Ровно O(n2)
Я в (132) это и имел в виду.

Но если развернуть массив, будет O(N)
0 "Elems: 1000. Iterations: 999"
0 "Elems: 2000. Iterations: 1999"

Или это не O(N^2)? Че-т я запутался

(154) нарисуй график и посмотри

(155) Подтверждаю, O(n^2)
(2n)^2/n^2 = 4
чудеса

Все равно я не понимаю, где тот алгоритм, который за O(N) решает
вот автор говорит, потом ищем максимум справа/слева от масимума, но потом его еще и еще надо искать ведь
получаются те же O(N^2)
вот для подобных случаев: https://cdn1.radikalno.ru/uploads/2020/5/26/ae38d6d3dc59165b2a3ebffc4e303b5c-full.png

нашел, спасибо за задачу, вообще огонь решение:

https://tproger.ru/problems/water-accumulated-in-puddles-between-walls/

(158) мне кажется, что приведенное там решение "в один проход" не сработает для случая 2 и более "стаканов"

я мееедленно запускаю IDEA...

(159) да нет, сработает
как всегда всё просто, уровни стаканов все время поднимаются к максимуму

надо же - работает!

2 строчки поменять - и можно получить массив заполнения воды.

(158) а если несколько локальных экстремумов?
32172312
когда у нас не один стакан с неровным дном а конфигурация разбивается на несколько стаканов с отбитым краем. и тоже неровным дном.

(157) и ничем не отличается от предложенных мной

(157)(158) В (85) же было.

(51) Я проверил. Работает.
А тут форум 1с-ников, а не js-ников.
Да, это не самый оптимальный вариант. Просто на скорую руку набросал.

(0) Если до (85) как говоришь сам за 15 минут догадался, то респект.

(91) Без нахождения максимума за один проход не получится.

Но вообще все эти задачки на собеседованиях если на джуна - я еще могу понять. А на мидла - уже как-то странно.

(169) встречайте говнокод, особо не старался, но полчаса или больше убил. Привет, карантин)

    Массив = Новый Массив;
    
    Массив.Добавить(1);
    Массив.Добавить(0);
    Массив.Добавить(5);
    Массив.Добавить(5);
    Массив.Добавить(0);
    Массив.Добавить(1);
    Массив.Добавить(17);
    Массив.Добавить(0);
    Массив.Добавить(3);
    Массив.Добавить(1);
    Массив.Добавить(0);
    Массив.Добавить(3);
    Массив.Добавить(1);
    Массив.Добавить(1);
    Массив.Добавить(0);
    
    ВсегоВоды = 0;

    Встретились = Ложь;
    
    ЛевыйКрайПорядок = 0;
    ЛевыйКрай = Массив[ЛевыйКрайПорядок];
    ЛевыйИтератор = ЛевыйКрайПорядок;
    ПройденоСлева = 0;
    ПройденоЭтажейСлева = 0;
    
    ПравыйКрайПорядок = Массив.Количество()-1;
    ПравыйКрай = Массив[ПравыйКрайПорядок];
    ПравыйИтератор = ПравыйКрайПорядок;
    ПройденоСправа = 0;
    ПройденоЭтажейСправа = 0;
    
    КрайИзменится = Ложь;
    
    КоличествоЭлементовМассива = Массив.Количество();
    
    Пока Не Встретились Цикл
        
        //Шаг вперед
        ТипШага = ?(ЛевыйКрай>ПравыйКрай,"Справа","Слева");
        
        Если ТипШага = "Слева" Тогда
            ЛевыйИтератор = ЛевыйИтератор + 1;
            ПройденоСлева = ПройденоСлева +1;
            
            Если Массив[ЛевыйИтератор] > ПравыйКрай ИЛИ Массив[ЛевыйИтератор] > ЛевыйКрай Тогда
                КрайИзменится = Истина;
                ПройденоЭтажейСлева = ПройденоЭтажейСлева;
            Иначе
                КрайИзменится = Ложь;
                ПройденоЭтажейСлева = ПройденоЭтажейСлева + Массив[ЛевыйИтератор];
            КонецЕсли;
        Иначе
            ПравыйИтератор = ПравыйИтератор - 1;
            ПройденоСправа = ПройденоСправа + 1;
            
            Если Массив[ПравыйИтератор] > ЛевыйКрай ИЛИ Массив[ПравыйИтератор] > ПравыйКрай Тогда
                КрайИзменится = Истина;
                ПройденоЭтажейСправа = ПройденоЭтажейСправа;
            Иначе
                КрайИзменится = Ложь;
                ПройденоЭтажейСправа = ПройденоЭтажейСправа + Массив[ПравыйИтератор];
            КонецЕсли;
        КонецЕсли;
        
        //Расчет воды
        Если КрайИзменится Тогда
            Если ТипШага = "Слева" Тогда
                ВсегоВоды = ВсегоВоды + (ПройденоСлева-1)*ЛевыйКрай - ПройденоЭтажейСлева;
                ЛевыйКрай = Массив[ЛевыйИтератор];
                ЛевыйКрайПорядок = ЛевыйИтератор;
                ПройденоСлева = 0;
                ПройденоЭтажейСлева = 0;
            Иначе
                ВсегоВоды = ВсегоВоды + (ПройденоСправа-1)*ПравыйКрай - ПройденоЭтажейСправа;
                ПравыйКрай = Массив[ПравыйИтератор];
                ПравыйКрайПорядок = ПравыйИтератор;
                ПройденоСправа = 0;
                ПройденоЭтажейСправа = 0;
            КонецЕсли
        КонецЕсли;
        
        Если ЛевыйИтератор+1 = ПравыйИтератор Тогда
            Встретились = Истина;
        КонецЕсли;
        
    КонецЦикла;
    
    //Загрушка Левого и Правого итератора - последнего стакана
    КоличествоИтерацийЗагрушки = ПравыйКрайПорядок-ЛевыйКрайПорядок-1;    
    КоличествоЭтажей = 0;
    Для Счетчик = (ЛевыйКрайПорядок+1) По ЛевыйКрайПорядок+КоличествоИтерацийЗагрушки Цикл
        КоличествоЭтажей = КоличествоЭтажей + Массив[Счетчик];
        //КоличествоИтерацийЗагрушки = КоличествоИтерацийЗагрушки + 1;
    КонецЦикла;
    
    ВсегоВоды = ВсегоВоды + Мин(ПравыйКрай,ЛевыйКрай) * КоличествоИтерацийЗагрушки - КоличествоЭтажей;
    
    Сообщить(ВсегоВоды);

(171) Как работает - пока до конца не понял (что за случай в конце обрабатывается). Но работает вроде как заявлено. Так что респект.

(172) основная идея - шагать вперёд с двух сторон от максимума до следующего максимума и рассчитывать сколько лезет в кусок между этим отрезком, триггер - переменная КрайИзменится как знак того, что надо рассчитать кусок от предыдущего максимума до следующего, загвоздка в том, что в последней итерации край не меняется, они просто встречаются и последний стакан остаётся не рассчитанным
Заглушка рассчитывает промежуток между последним стаканом(или первым, если он один)
Хмм, только заметил опечатку "загрушка")

(173) от одного локального максимума, до другого как оказалось неверное решение

Но и это (171) решение не идеальное, как максимум, она может также пройтись два раза по циклу - в том случае, если стакан в итоге один, не могу додумать механизм как все сделать в одном цикле)

Хотя, пока писал этот коммент понял, что последний цикл всего лишь считает количество этажей внутри стакана, а они определены как переменные "пройденоэтажейсправа" и "пройденоэтажейслева", тогда можно не бегать последний раз по циклу, может в основном теле надо поиграться с итераторами, но работать будет

(174) Мне тоже казалось, что неверное. Но (171) проходит тесты. Появится время - разберусь в чем фишка.

Массив = Новый Массив;
    
Массив.Добавить(1);
Массив.Добавить(0);
Массив.Добавить(5);
Массив.Добавить(5);
Массив.Добавить(0);
Массив.Добавить(1);
Массив.Добавить(17);
Массив.Добавить(0);
Массив.Добавить(3);
Массив.Добавить(1);
Массив.Добавить(0);
Массив.Добавить(3);
Массив.Добавить(1);
Массив.Добавить(1);
Массив.Добавить(0);
    
ВсегоВоды = 0;
ПерваяГраница = 0;
ПерваяПоз = 0;
    
к=0;
Пока к<=Массив.Количество()-1 Цикл
    Если ПерваяГраница<=Массив[к] Тогда
    ПерваяГраница = Массив[к];
    ПерваяПоз = к;            
    Иначе
    МаксВысота = Массив[к];
    ПозМаксВысоты = к;
            
    СчитатьПоМаксВысоте = Истина;
            
    Для н=к+1 По Массив.Количество()-1 Цикл
                
        Если ПерваяГраница<=Массив[н] Тогда                                        
        Предел = Мин(ПерваяГраница,Массив[н]);
                    
        Для р=ПерваяПоз+1 По н-1 Цикл
                        
            ВсегоВоды = ВсегоВоды+(Предел-Массив[р]);    
                        
        КонецЦикла;    
                    
        ПерваяГраница = Массив[н];
        ПерваяПоз = н;
        к = ПерваяПоз;
        СчитатьПоМаксВысоте = Ложь;
                    
        Прервать;
                    
        Иначе    
                                    
        Если Массив[н]>МаксВысота Тогда
                        
            МаксВысота = Массив[н];
            ПозМаксВысоты = н;
                        
            КонецЕсли;    
                    
        КонецЕсли;
                                
    КонецЦикла;    
            
    Если СчитатьПоМаксВысоте Тогда
                
        Предел = Мин(ПерваяГраница,МаксВысота);
                
        Для р=ПерваяПоз+1 По ПозМаксВысоты-1 Цикл
                    
        ВсегоВоды = ВсегоВоды+(Предел-Массив[р]);    
                    
        КонецЦикла;    
                
        ПерваяГраница = МаксВысота;
        ПерваяПоз = ПозМаксВысоты;
        к = ПерваяПоз;
                
    КонецЕсли;    
            
    КонецЕсли;
        
    к=к+1;
                
КонецЦикла;
    
Сообщить(ВсегоВоды);

(0) Интересная задачка.
Проще всего решается через заполнение двухмерного массива, так сказать методом эмуляции.

Для 5 1 3 0 4 массив будет 5х5

X0000
X000X
X0X0X
X0X0X
XXX0X

Домики нарисовали, осталось заполнить водой

X0000
X111X
X1X1X
X1X1X
XXX1X

И посчитать кол-во 1

Приколы возникают что надо эмулировать стекание воды
Например если

X00000
X000X0
X0X0X0
X0X0X0
XXX0XX

То заполнение будет только внутри домов, снаружи вода "стечет"

X00000
X111X0
X1X1X0
X1X1X0
XXX1XX


(178) И в каком месте упрощение? Каков будет алгоритм "эмуляции заполнения"?

А, типа пробегаться каждый раз по горизонталям?

(180) Итерационный добавляем во все нижние клетки 0 воду и эмулируем набор воды с вытеснением-стеканием.
Как только несколько циклов картинка не меняется - все заполнилось.

(182)+ Хотя еще проще, все клетки 0 заполняем 1 и далее алгоритм стекания, стенки считаем что прозрачны

(182) Предлагаю упростить до реальной физической модели на дифурах. Будет частный случай от стекания воды в риал-тайме.
"Тем самым сведя задачу к предыдущей" (с)

(184) Зачем дифуры когда можно молекулы эмулировать с броуновским движением ))

(185) 1С тормозить начнет

(185) точно, там будет лагранжиан второго рода, а это урчп, что не диффуры

(186) По условиям задачи молекулы очень крупные размером с этаж дома ))

Броуновское движение этажей дома - это страшно.

Короче клеточный автомат банальный