В чем неправильный мой алгоритм решения проблемы запасов? ⇐ JAVA

[Anonymous]

Вопрос:
Проблема диапазона цен на акции — это финансовая задача, в которой у нас есть серия из n ежедневных котировок цен на акции, и нам нужно вычислить диапазон цен на акции для всех n дней.
Размах Si цены акций в данный день i определяется как максимальное количество последовательных дней непосредственно перед данным днем, для которых цена акции в данный день меньше или равна к его цене на текущий день.
Например, если массив цен за 7 дней задан как {100, 80, 60, 70, 60, 75, 85}, то значения интервала для соответствующих 7 дней равны {1, 1, 1, 2, 1, 4, 6}.
Мое решение:

Код: Выделить всё

class Solution {

public static int[] calculateSpan(int price[], int n) {
Stack s1 = new Stack();
Stack s2 = new Stack();
int[] count = new int[price.length];

for(int i = 0 ; i < n; i++) {
int size = 0;

while(!s1.empty() && price[i] > s1.peek()) {
s2.push(s1.pop());
}
if(!s2.empty()) {
size = s2.size();
}
while(!s2.empty() && price[i] > s2.peek()) {
s1.push(s2.pop());
}

s1.push(price[i]);
count[i] = size + 1;
}

return count;
}
}

Для ввода:

Код: Выделить всё

n = 134
74 665 742 512 254 469 748 445 663 758 38 60 724 142 330 779 317 636 591 243 289 507 241 143 65 249 247 606 691 330 371 151 607 702 394 349 430 624 85 755 357 641 167 177 332 709 145 440 627 124 738 739 119 483 530 542 34 716 640 59 305 331 378 707 474 787 222 746 525 673 671 230 378 374 298 513 787 491 362 237 756 768 456 375 32 53 151 351 142 125 367 231 708 592 408 138 258 288 554 784 546 110 210 159 222 189 23 147 307 231 414 369 101 592 363 56 611 760 425 538 749 84 396 42 403 351 692 437 575 621 597 22 149 800

Мой результат:

Код: Выделить всё

1 2 3 1 1 2 7 1 2 10 1 2 3 1 2 16 1 2 1 1 2 3 1 1 1 4 1 10 13 1 2 1 4 18 1 1 3 4 1 24 1 2 1 2 3 6 1 2 3 1 11 12 1 2 3 4 1 6 1 1 2 3 4 6 1 66 1 2 1 2 1 1 2 1 1 5 11 1 1 1 4 5 1 1 1 2 3 4 1 1 7 1 11 1 1 1 2 3 5 23 1 1 2 1 4 1 1 2 8 1 10 1 1 14 1 1 17 18 1 2 3 1 2 1 4 1 6 1 2 3 1 1 2 134

а ожидаемый результат:

Код: Выделить всё

1 2 3 1 1 2 7 1 2 10 1 2 3 1 2 16 1 2 1 1 2 3 1 1 1 4 1 10 13 1 2 1 4 18 1 1 3 4 1 24 1 2 1 2 3 6 1 2 3 1 11 12 1 2 3 4 1 6 1 1 2 3 4 6 1 66 1 2 1 2 1 1 2 1 1 5 77 1 1 1 4 5 1 1 1 2 3 4 1 1 7 1 11 1 1 1 2 3 5 23 1 1 2 1 4 1 1 2 8 1 10 1 1 14 1 1 17 18 1 2 3 1 2 1 4 1 6 1 2 3 1 1 2 134

Разница в том, что одно значение в выводе — 77, а мое — 11.
Я отлаживал это последние 5 часов, но не смог понять.
Буду очень признателен за помощь в понимании проблемы.
Примечание: я знаю, что мы можем сделать это с помощью 1 стека и различных других оптимизированных подходов. . Но я просто хочу знать, насколько мой подход неверен? Что не так в моем алгоритме?

Подробнее здесь: https://stackoverflow.com/questions/787 ... -incorrect