План курса / Все задачи / Алгоритмы и структуры данных

Подставной отчет

средне

# решено

Дан массив stock, где stock[i] = 1 означает рост акций в i-й день, а stock[i] = 0 — падение.

Компания терпит убытки и готовит отчет для инвесторов, в котором можно улучшить показатели, заменив один день падения (0) на рост (1).

Требуется найти максимальное количество подряд идущих дней роста акций с учетом такой замены.

Нумерация в массиве начинается с единицы, а не с нуля.

Пример 1:

Ввод: stock = [1,1,0,1,1,1,1,0,1]
Вывод: 7
Объяснение: самый долгий рост акций с 1 по 7 день с заменой в 3 дне.

Пример 2:

Ввод: stock = [0]
Вывод: 1

Пример 3:

Ввод: stock = [1,0,0,1]
Вывод: 2

Ограничения:

0 <= len(stock)
Значение массива stock : 0 или 1

Решение (более "красивое")

using System;
using System.Collections.Generic;

public class Solution
{
    public static int LongestStockGrowth(List<int> stock)
    {
        int maxCount = 0;  // максимальное количество подряд идущих единиц
        int count = 0;     // текущее количество подряд идущих единиц
        int prev = 0;      // количество единиц до последнего нуля
        
        foreach (var num in stock)
        {
            if (num == 1)
            {
                count++;
            }
            else
            {
                // встретили ноль — текущая серия становится предыдущей
                prev = count;
                count = 0;
            }
            
            // prev + 1 (замена нуля) + count
            maxCount = Math.Max(maxCount, prev + 1 + count);
        }
        
        // если нулей не было, нельзя ничего заменить
        return Math.Min(maxCount, stock.Count);
    }
}

#include <vector>
#include <algorithm>

using namespace std;

int longestStockGrowth(vector<int> stock) {
    int maxCount = 0;  // максимальное количество подряд идущих единиц
    int count = 0;     // текущее количество подряд идущих единиц
    int prev = 0;      // количество единиц до последнего нуля
    
    for (int num : stock) {
        if (num == 1) {
            count++;
        } else {
            // встретили ноль — текущая серия становится предыдущей
            prev = count;
            count = 0;
        }
        
        // prev + 1 (замена нуля) + count
        maxCount = max(maxCount, prev + 1 + count);
    }
    
    // если нулей не было, нельзя ничего заменить
    return min(maxCount, (int)stock.size());
}

package main

func longestStockGrowth(stock []int) int {
    maxCount := 0  // максимальное количество подряд идущих единиц
    count := 0     // текущее количество подряд идущих единиц
    prev := 0      // количество единиц до последнего нуля
    
    for _, num := range stock {
        if num == 1 {
            count++
        } else {
            // встретили ноль — текущая серия становится предыдущей
            prev = count
            count = 0
        }
        
        // prev + 1 (замена нуля) + count
        if prev+1+count > maxCount {
            maxCount = prev + 1 + count
        }
    }
    
    // если нулей не было, нельзя ничего заменить
    if maxCount > len(stock) {
        return len(stock)
    }
    return maxCount
}

import java.util.*;

public class Solution {
    public int longestStockGrowth(List<Integer> stock) {
        int maxCount = 0;  // максимальное количество подряд идущих единиц
        int count = 0;     // текущее количество подряд идущих единиц
        int prev = 0;      // количество единиц до последнего нуля
        
        for (int num : stock) {
            if (num == 1) {
                count++;
            } else {
                // встретили ноль — текущая серия становится предыдущей
                prev = count;
                count = 0;
            }
            
            // prev + 1 (замена нуля) + count
            maxCount = Math.max(maxCount, prev + 1 + count);
        }
        
        // если нулей не было, нельзя ничего заменить
        return Math.min(maxCount, stock.size());
    }
}

from typing import *

def longest_stock_growth(stock: List[int]) -> int:
    max_count = 0   # максимальное количество подряд идущих единиц
    count = 0       # текущее количество подряд идущих единиц
    prev = 0        # количество единиц до последнего нуля
    
    for num in stock:
        if num == 1:
            count += 1
        else:
            # встретили ноль — текущая серия становится предыдущей
            prev = count
            count = 0
        
        # prev + 1 (замена нуля) + count
        max_count = max(max_count, prev + 1 + count)
    
    # если нулей не было, нельзя ничего заменить
    return min(max_count, len(stock))

/**
 * @param {number[]} stock
 * @returns {number}
 */
export function longestStockGrowth(stock) {
  let maxCount = 0;  // максимальное количество подряд идущих единиц
  let count = 0;     // текущее количество подряд идущих единиц
  let prev = 0;      // количество единиц до последнего нуля
  
  for (const num of stock) {
    if (num === 1) {
      count++;
    } else {
      // встретили ноль — текущая серия становится предыдущей
      prev = count;
      count = 0;
    }
    
    // prev + 1 (замена нуля) + count
    maxCount = Math.max(maxCount, prev + 1 + count);
  }
  
  // если нулей не было, нельзя ничего заменить
  return Math.min(maxCount, stock.length);
}

Оценка сложности

Время: O(n), где n - длина массива stock
Память: O(1)

Решение (с использованием паттерна)

public class Solution
{
    public static int LongestStockGrowth(List<int> stock)
    {
        int l = 0;
        // r = -1, чтобы добавление первого элемента не было исключением
        int r = -1;
        int result = 0;
        int zerosCount = 0;
        int zeroIdx = 0;

        while (l < stock.Count)
        {
            while (r + 1 < stock.Count && (stock[r + 1] == 1 || zerosCount < 1))
            {
                if (stock[r + 1] == 0)
                {
                    // запоминаем индекс нуля, который добавляем в окно
                    zeroIdx = r + 1;
                    zerosCount += 1;
                }
                r += 1;
            }

            // обновляем ответ
            int windowSize = r - l + 1;
            result = Math.Max(result, windowSize);

            // сдвигаем на zeroIdx, когда у нас есть 0 в окне
            // сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
            zerosCount = 0;
            l = Math.Max(zeroIdx + 1, l + 1);
        }
        return result;
    }
}

#include <algorithm>
#include <vector>

using namespace std;

int longestStockGrowth(const vector<int>& stock) {
    int l = 0;
    // r = -1, чтобы добавление первого элемента не было исключением
    int r = -1;
    int result = 0;
    int zerosCount = 0;
    int zeroIdx = 0;

    while (l < stock.size()) {
        while (r + 1 < stock.size() && (stock[r + 1] == 1 || zerosCount < 1)) {
            if (stock[r + 1] == 0) {
                // запоминаем индекс нуля, который добавляем в окно
                zeroIdx = r + 1;
                zerosCount += 1;
            }
            r += 1;
        }
        
        // обновляем ответ
        int windowSize = r - l + 1;
        result = max(result, windowSize);

        // сдвигаем на zeroIdx, когда у нас есть 0 в окне
        // сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
        zerosCount = 0;
        l = max(zeroIdx + 1, l + 1);
    }
    return result;
}

package main

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func longestStockGrowth(stock []int) int {
    l := 0
    // r = -1, чтобы добавление первого элемента не было исключением
    r := -1
    result := 0
    zerosCount := 0
    zeroIdx := 0

    for l < len(stock) {
        for r + 1 < len(stock) && (stock[r + 1] == 1 || zerosCount < 1) {
            if stock[r + 1] == 0 {
                // запоминаем индекс нуля, который добавляем в окно
                zeroIdx = r + 1
                zerosCount += 1
            }
            r += 1
        }
        
        // обновляем ответ
        windowSize := r - l + 1
        result = max(result, windowSize)

        // сдвигаем на zeroIdx, когда у нас есть 0 в окне
        // сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
        zerosCount = 0
        l = max(zeroIdx + 1, l + 1)
    }
    return result
}

import java.util.*;

class Solution {
    public int longestStockGrowth(List<Integer> stock) {
        int l = 0;
        // r = -1, чтобы добавление первого элемента не было исключением
        int r = -1;
        int result = 0;
        int zerosCount = 0;
        int zeroIdx = 0;

        while (l < stock.size()) {
            while (r + 1 < stock.size() && (stock.get(r + 1) == 1 || zerosCount < 1)) {
                if (stock.get(r + 1) == 0) {
                    // запоминаем индекс нуля, который добавляем в окно
                    zeroIdx = r + 1;
                    zerosCount += 1;
                }
                r += 1;
            }
            
            // обновляем ответ
            int windowSize = r - l + 1;
            result = Math.max(result, windowSize);

            // сдвигаем на zeroIdx, когда у нас есть 0 в окне
            // сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
            zerosCount = 0;
            l = Math.max(zeroIdx + 1, l + 1);
        }
        return result;
    }
}

from typing import *

def longest_stock_growth(stock: List[int]) -> int:
    l = 0
    # r = -1, чтобы добавление первого элемента не было исключением
    r = -1
    result = 0
    zerosCount = 0
    zeroIdx = 0

    while l < len(stock):
        while r + 1 < len(stock) and (stock[r + 1] == 1 or zerosCount < 1):
            if stock[r + 1] == 0:
                zerosCount += 1
                zeroIdx = r + 1
            r += 1
        
        # обновляем ответ
        windowSize = r - l + 1
        result = max(result, windowSize)

        # сдвигаем на zeroIdx, когда у нас есть 0 в окне
        # сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
        zerosCount = 0
        l = max(zeroIdx + 1, l + 1)
    return result

export function longestStockGrowth(stock) {
    let l = 0;
    // r = -1, чтобы добавление первого элемента не было исключением
    let r = -1;
    let result = 0;
    let zerosCount = 0;
    let zeroIdx = 0;

    while (l < stock.length) {
        while (r + 1 < stock.length && (stock[r + 1] === 1 || zerosCount < 1)) {
            if (stock[r + 1] === 0) {
                // запоминаем индекс нуля, который добавляем в окно
                zeroIdx = r + 1;
                zerosCount += 1;
            }
            r += 1;
        }

        // обновляем ответ
        let windowSize = r - l + 1;
        result = Math.max(result, windowSize);

        // сдвигаем на zeroIdx, когда у нас есть 0 в окне
        // сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
        zerosCount = 0;
        l = Math.max(zeroIdx + 1, l + 1);
    }
    return result;
}

Оценка сложности

Время: O(n), где n - длина массива stock
Память: O(1)

Задача паттерна - выступать универсальным средством решения задач, но из-за этого бывают ситуации, когда код выглядит не так красиво как альтернативное решение. Тем не менее это универсальный инструмент, который советую освоить!

На собеседовании примут оба решения, но первое считается именно для этой задачи более каноничным и приоритетным.