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

Рост акций компании

средне

# решено

Дан массив stock, где stock[i] = 1 означает рост акций в i-й день, а stock[i] = -1 — падение. Требуется найти максимальное количество подряд идущих дней роста акций.

Пример 1:

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

Пример 2:

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

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

0 <= len(stock)
Значение массива stock это -1 или 1

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

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

        return maxCount;
    }
}

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

        return maxCount;
    }
}

#include <algorithm>
#include <vector>

using namespace std;

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

import java.util.*;

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

from typing import *

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

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

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

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

Решение (через плавающее окно)

public class Solution
{
    public static int LongestStockGrowth(List<int> stock)
    {
        int l = 0;
        int r = 0;
        int result = 0;

        while (l < stock.Count)
        {
            while (r + 1 < stock.Count && stock[r] == stock[r + 1])
            {
                r += 1;
            }

            if (stock[r] == 1)
            {
                result = Math.Max(result, r - l + 1);
            }

            l = r + 1;
            r = r + 1;
        }

        return result;
    }
}

#include <algorithm>
#include <vector>

using namespace std;

int longestStockGrowth(const vector<int>& stock) {
    int l = 0;
    int r = 0;
    int result = 0;
    while (l < stock.size()) {
        while (r + 1 < stock.size() && stock[r] == stock[r + 1]) {
            r += 1;
        }

        if (stock[r] == 1) {
            result = max(result, r - l + 1);
        }

        l = r + 1;
        r = r + 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 := 0
    result := 0
    for l < len(stock) {
        for r + 1 < len(stock) && stock[r] == stock[r + 1] {
            r += 1
        }

        if stock[r] == 1 {
            result = max(result, r - l + 1)
        }

        l = r + 1
        r = r + 1
    }
    return result
}

import java.util.*;

class Solution {
    public int longestStockGrowth(List<Integer> stock) {
        int l = 0;
        int r = 0;
        int result = 0;
        while (l < stock.size()) {
            while (r + 1 < stock.size() && stock.get(r) == stock.get(r + 1)) {
                r += 1;
            }

            if (stock.get(r) == 1) {
                result = Math.max(result, r - l + 1);
            }

            l = r + 1;
            r = r + 1;
        }
        return result;
    }
}

from typing import *

def longest_stock_growth(stock: List[int]) -> int:
    l = 0
    r = 0
    result = 0
    while l < len(stock):
        while r + 1 < len(stock) and stock[r] == stock[r + 1]:
            r += 1

        if stock[r] == 1:
            result = max(result, r - l + 1)

        l = r + 1
        r = r + 1
    return result

/**
 * @param {number[]} stock
 * @returns {number}
 */
export function longestStockGrowth(stock) {
  let l = 0;
  let r = 0;
  let result = 0;

  while (l < stock.length) {
    while (r + 1 < stock.length && stock[r] === stock[r + 1]) {
      r += 1;
    }

    if (stock[r] === 1) {
      result = Math.max(result, r - l + 1);
    }

    l = r + 1;
    r = r + 1;
  }

  return result;
}

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

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