В чем неправильный мой алгоритм решения проблемы запасов?
Вопрос :
Проблема диапазона акций — это финансовая задача, в которой у нас есть серия из 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<Integer> s1 = new Stack<>();
Stack<Integer> 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 часов, но не смог понять. Буду очень признателен за помощь в понимании вопроса.
Примечание: я знаю, что мы можем сделать это с помощью одного стека и различных других оптимизированных подходов. Но я просто хочу знать, насколько мой подход неверен? Что не так в моем алгоритме?
[РЕДАКТИРОВАТЬ] Исходный вопрос здесь: https://www.geeksforgeeks.org/problems/stock-span-problem-1587115621/1
Ответы 2
public static int[] calculateSpan(int price[], int n) {
Stack<Integer> stack = new Stack<>();
int[] span = new int[n];
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && price[i] >= price[stack.peek()]) {
stack.pop();
}
span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
return span;
}
Я специально просил не давать оптимизированное решение или что-то в этом роде, а указать, почему мой код неверен!
Глядя на входные данные и до разницы, которую вы имеете:
Input:
..... 305 331 378 707 474 787 222 746 525 673 671 230 378 374 298 513 787
^^^
Different
result
here
Итак, у вас 11, а ожидаемый результат — 77.
Итак, давайте посчитаем в обратном порядке от точки отказа.
Input:
..... 305 331 378 707 474 787 222 746 525 673 671 230 378 374 298 513 787
11 10 9 8 7 6 5 4 3 2 1
Теперь обратите внимание, что значение в месте сбоя равно 787. Кроме того, обратите внимание, что значение непосредственно перед вашим результатом (11) также равно 787.
Это убедительно свидетельствует о том, что ваш алгоритм неправильно обрабатывает равенство.
Глядя на ваш код, все сравнения price выполняются с использованием >. Рассмотрите возможность замены одного (или нескольких) на >=
Да. Я обновил вопрос.