Итак, я решал проблему падающих квадратов.

На ось X 2D-плоскости помещается несколько квадратов.

Вам дается 2D целочисленный массив позиций, в котором позиции[i] = [lefti, длина стороны] представляют собой i-й квадрат с длиной стороны, равной длине стороны, который отбрасывается, его левый край выровнен по координате X слева.

Каждый квадрат сбрасывается по одному за раз с высоты над любыми приземлившимися квадратами. Затем он падает вниз (отрицательное направление Y), пока не упадет либо на верхнюю сторону другого квадрата, либо на ось X. Квадрат, задевающий левую/правую сторону другого квадрата, не считается приземлением на него. Как только он приземляется, он застывает на месте и не может быть перемещен.

После того, как каждый квадрат будет сброшен, вы должны записать высоту текущей самой высокой стопки квадратов.

Возвращает массив целых чисел ans, где ans[i] представляет высоту, описанную выше, после удаления i-го квадрата.

Мыслительный процесс:

1. Инициализируйте и запомните первые точки(координаты x и y).
2. Повторяйте один за другим, и если ящики лежат друг на друге ,добавьте высоту.
3. Если это не так, посмотрите, какая из текущих высот или max_height больше, и добавьте ее в результирующий список.

Это мой код :

 class Solution:
    def falling_squares(self, positions: List[List[int]]) -> List[int]:
        x_coordinate = positions[0][0]
        y_coordinate = positions[0][1]
        max_height = y_coordinate
        result = [max_height]
        for left,position in positions[1:]:
            if left<x_coordinate y_coordinate:
                max_height =position
                result.append(max_height)
            else:
                max_height = max(max_height,position)
                result.append(max_height)
            x_coordinate=left
            y_coordinate = position
        return result 
 

Это и есть результат

Пожалуйста, скажите мне, чего мне не хватает в моей логике.

У вас много ошибок в вашем коде, я пытался улучшить его, исправив некоторую логику, но в других тестовых наборах leetcode, которые вы дали, появлялась еще одна логическая ошибка. В итоге я переписал код заново.

 class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        ret = []
        blocks = {}
        for drop in positions:
            x_coordinate = drop[0]
            checked = False
            elongation = drop[1]
            for (block_x, block_xe), prev_h in blocks.copy().items():
                if x_coordinate < block_xe and x_coordinate elongation > block_x:
                    if blocks.get((x_coordinate,x_coordinate   elongation)):
                        if blocks.get((x_coordinate,x_coordinate   elongation)) < elongation   prev_h:
                            blocks[(x_coordinate,x_coordinate   elongation)] = elongation  prev_h
                    else:
                        blocks[(x_coordinate,x_coordinate   elongation)] = elongation  prev_h
                    checked = True
            if not checked:
                blocks[(x_coordinate, x_coordinate elongation)] = elongation
            ret.append(max(blocks.values()))
        return ret
 

Вот объяснение:

строка 1: инициализация списка возврата.

строка 2: инициализация хэш — карты для блоков. Причина, по которой я просто не сделал то, что сделали вы, заключалась в том, что в некоторых случаях блок приземляется на блок, который был записан несколько итераций назад, а не только на предыдущей итерации, и его высота больше max_height. Кроме того, это была главная причина, побудившая меня переписать ваш код.

строка 7: повторение копии blocks , потому что я изменяю ее в цикле.

строка 8-15: проверка того, меньше ли x блока, чем x второго блока его удлинение, и проверка того, больше ли x блока его удлинение, чем x второго блока. Это делается для проверки того, приземляется ли блок поверх любого другого блока.

проверка наличия дубликата текущего блока. Если да, то мы добавим его только в том случае, если он больше, чем его обманут. В противном случае, если нет дублирования, которое просто добавляет его.

строка 17: если блок приземлился на любой другой блок , то checked он переключается True , если нет, то мы добавляем его в хэш-карту.

Очевидно, есть более быстрый способ сделать это:

 Runtime: 883 ms, faster than 26.06% of Python3 online submissions for Falling Squares.
Memory Usage: 15 MB, less than 51.41% of Python3 online submissions for Falling Squares.