Три в ряд

средне

# решено

Дан массив чисел colors, где colors[i] — цвет шара на позиции i. Если три или более шаров одного цвета стоят подряд, они схлопываются. Нужно вернуть общее количество шаров, которые схлопнутся.

После схлопывания шаров, оставшиеся шары могут снова образовать последовательность из трёх или более одинаковых цветов, что также приведёт к их схлопыванию.

Пример 1:

Ввод: colors = [1,1,2,2,2,1]
Вывод: 6
Объяснение: сначала схлопнутся двойки, а потом единички

Пример 2:

Ввод: colors = [4,1,2,3,3,3,2,2,1,1]
Вывод: 9

Пример 3:

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

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

len(colors) >= 1

public class Solution
{
    public static int Play(List<int> colors)
    {
        Stack<int> stack = new Stack<int>();
        int result = 0;

        foreach (int num in colors)
        {
            if (stack.Count >= 2 && stack.Peek() == num)
            {
                int top1 = stack.Pop();
                int top2 = stack.Peek();

                if (top2 == num)
                {
                    // Три подряд одинаковых — схлопываем
                    result += 3;
                    stack.Pop();
                    continue;
                }
                else
                {
                    stack.Push(top1);
                }
            }

            stack.Push(num);
        }

        return result;
    }
}

#include <vector>

using namespace std;

int play(const vector<int>& colors) {
    vector<int> stack;
    int result = 0;

    for (int num : colors) {
        if (stack.size() >= 2 && stack.back() == num && stack[stack.size() - 2] == num) {
            // три подряд одинаковых — схлопываем
            result += 3;
            stack.pop_back();
            stack.pop_back();
            continue;
        }
        stack.push_back(num);
    }
    return result;
}

package main

func play(colors []int) int {
    stack := []int{}
    result := 0

    for _, num := range colors {
        if len(stack) >= 2 && stack[len(stack)-1] == num && stack[len(stack)-2] == num {
            // три подряд одинаковых — схлопываем
            result += 3
            stack = stack[:len(stack)-2]
            continue
        }
        stack = append(stack, num)
    }
    return result
}

import java.util.*;

public class Solution {
    public int play(List<Integer> colors) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;

        for (int num : colors) {
            if (stack.size() >= 2 && stack.get(stack.size() - 1) == num && stack.get(stack.size() - 2) == num) {
                // три подряд одинаковых — схлопываем
                result += 3;
                stack.pop();
                stack.pop();
                continue;
            }
            stack.push(num);
        }
        return result;
    }
}

import java.util.*;

public class Solution {
    public int play(List<Integer> colors) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;

        for (int num : colors) {
            if (stack.size() >= 2 && stack.get(stack.size() - 1) == num && stack.get(stack.size() - 2) == num) {
                // три подряд одинаковых — схлопываем
                result += 3;
                stack.pop();
                stack.pop();
                continue;
            }
            stack.push(num);
        }
        return result;
    }
}

from typing import *

def play(colors: List[int]) -> int:
    stack = []
    result = 0
    for num in colors:
        if len(stack) >= 2 and stack[-1] == num and stack[-2] == num:
            # три подряд одинаковых — схлопываем
            result += 3
            stack.pop()
            stack.pop()
            continue
        stack.append(num)
    return result

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

Время: O(n), где n - размер массива colors
Память: O(n), где n - размер массива colors