например - 2,4,1,2,0,3. stack =(2,4), l=2; stack(2,4)(1,2), l=1; И сейчас подходим к 0, и если по вашему алгоритму сначала положить на стэк последний интервал - (0, 3) и потом далее по писку перейти в else(ваш алгоритм), берём мин на стэке - это 0(L=0), "Чистим стек от интервалов, снимая с вершины, для которых текущее число больше r", сейчас на стэке (0,3), текущее 3. В итоге ничего не снимаем со стэка и конец списка. То есть вернём false? Хотя должно быть true.
Вот, что он мне печатает для этого примера:
2
{(2,2),}
4
{(2,4),}
1
{(2,4),(1,1),}
2
{(2,4),(1,2),}
0
{(2,4),(1,2),(0,0),}
- элемент 2, стек пустой, кладем точку на стек (2,2)
- элемент 4, стек не пустой и текущий элемент (4) больше 2 (left) на вершине стека
- запоминаем 2, чистим стек (в итоге пустой), создаем новый интервал (2,4) и кладем на стек
- элемент 1, стек не пустой и текущий элемент (1) меньше 2 (left) на вершине стека
- создаем новый вырожденный интервал и кладем на стек
- элемент 2, стек не пустой и текущий элемент (2) больше 1 (left) на вершине стека
- запоминаем 1, чистим стек (в итоге {(2,4),})
- подходим ли 2 в текущий интервал под ответ? нет, создаем новый интервал (1,2) и кладем на стек
- элемент 0, стек не пустой и текущий элемент (0) меньше 1 (left) на вершине стека
- создаем новый вырожденный интервал и кладем на стек
- элемент 3, стек не пустой и текущий элемент (3) больше 0 (left) на вершине стека
- запоминаем 0, чистим стек (в итоге {(2,4),})
- подходит ли этот интервал под ответ? да (2,4,3), возвращаем true