План курса / Все задачи / Алгоритмы и структуры данных
Наглый подставной отчет
средне
# решено
Дан массив stock, где stock[i] = 1 означает рост акций в i-й день, а stock[i] = 0 — падение.
Компания терпит убытки и готовит подставной отчет для инвесторов, в котором можно улучшить показатели, заменив до k дней падения (0) на рост (1).
Требуется найти максимальное количество подряд идущих дней роста акций с учетом такой замены.
Нумерация в массиве начинается с единицы, а не с нуля.
Пример 1:
Ввод: stock = [1,0,1,1,0,1,1,0], k = 2
Вывод: 7
Объяснение: самый долгий рост акций с 1 по 7 день с заменой в 2 и 5 днях.
Пример 2:
Ввод: stock = [1,0,0,1], k = 1
Вывод: 2
Пример 3:
Ввод: stock = [0], k = 0
Вывод: 0
Ограничения:
0 <= len(stock)
Значение массива stock : 0 или 1
public class Solution
{
public static int LongestStockGrowth(List<int> stock, int k)
{
int l = 0;
// r = -1, чтобы добавление первого элемента не было исключением
int r = -1;
int result = 0;
int zerosCount = 0;
while (l < stock.Count)
{
while (r + 1 < stock.Count && (stock[r + 1] == 1 || zerosCount < k))
{
zerosCount += stock[r + 1] == 0 ? 1 : 0;
r += 1;
}
// обновляем ответ
int windowSize = r - l + 1;
result = Math.Max(result, windowSize);
// сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
zerosCount -= stock[l] == 0 ? 1 : 0;
l += 1;
}
return result;
}
}
#include <algorithm>
#include <vector>
using namespace std;
int longestStockGrowth(const vector<int>& stock, int k) {
int l = 0;
// r = -1, чтобы добавление первого элемента не было исключением
int r = -1;
int result = 0;
int zerosCount = 0;
while (l < stock.size()) {
while (r + 1 < stock.size() && (stock[r + 1] == 1 || zerosCount < k)) {
zerosCount += int(stock[r + 1] == 0);
r += 1;
}
// обновляем ответ
int windowSize = r - l + 1;
result = max(result, windowSize);
// сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
zerosCount -= int(stock[l] == 0);
l = l + 1;
}
return result;
}
package main
func max(a, b int) int {
if a > b {
return a
}
return b
}
func longestStockGrowth(stock []int, k int) int {
l := 0
// r = -1, чтобы добавление первого элемента не было исключением
r := -1
result := 0
zerosCount := 0
for l < len(stock) {
for r + 1 < len(stock) && (stock[r + 1] == 1 || zerosCount < k) {
if stock[r + 1] == 0 {
zerosCount += 1
}
r += 1
}
// обновляем ответ
windowSize := r - l + 1
result = max(result, windowSize)
// сдвигаем на l + 1 с актуальной поддержкой числа нулей в окне
if stock[l] == 0 {
zerosCount -= 1
}
l = l + 1
}
return result
}
import java.util.*;
class Solution {
public int longestStockGrowth(List<Integer> stock, int k) {
int l = 0;
// r = -1, чтобы добавление первого элемента не было исключением
int r = -1;
int result = 0;
int zerosCount = 0;
while (l < stock.size()) {
while (r + 1 < stock.size() && (stock.get(r + 1) == 1 || zerosCount < k)) {
zerosCount += (stock.get(r + 1) == 0) ? 1: 0;
r += 1;
}
// обновляем ответ
int windowSize = r - l + 1;
result = Math.max(result, windowSize);
// сдвигаем на l + 1 учитывая новое число нулей в окне после сдвига
zerosCount += (stock.get(l) == 0) ? -1: 0;
l = l + 1;
}
return result;
}
}
from typing import *
def longest_stock_growth(stock: List[int], k: int) -> int:
l = 0
# r = -1, чтобы добавление первого элемента не было исключением
r = -1
result = 0
zerosCount = 0
while l < len(stock):
while r + 1 < len(stock) and (stock[r + 1] == 1 or zerosCount < k):
if stock[r + 1] == 0:
zerosCount += 1
r += 1
# обновляем ответ
windowSize = r - l + 1
result = max(result, windowSize)
# сдвигаем на l + 1 левую границу и поддерживаем
# актуальное число нулей в окне
zerosCount += -1 if stock[l] == 0 else 0
l = l + 1
return result
export function longestStockGrowth(stock, k) {
let l = 0;
// r = -1, чтобы добавление первого элемента не было исключением
let r = -1;
let result = 0;
let zerosCount = 0;
while (l < stock.length) {
while (r + 1 < stock.length && (stock[r + 1] === 1 || zerosCount < k)) {
zerosCount += stock[r + 1] === 0 ? 1 : 0;
r += 1;
}
// обновляем ответ
let windowSize = r - l + 1;
result = Math.max(result, windowSize);
// сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
zerosCount -= stock[l] === 0 ? 1 : 0;
l += 1;
}
return result;
}