Press "Enter" to skip to content

Posts tagged as “max”

花花酱 LeetCode 699. Falling Squares

题目大意:方块落下后会堆叠在重叠的方块之上,问每一块方块落下之后最高的方块的高度是多少?

Problem:

On an infinite number line (x-axis), we drop given squares in the order they are given.

The i-th square dropped (positions[i] = (left, side_length)) is a square with the left-most point being positions[i][0] and sidelength positions[i][1].

The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next.

The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.

 

Return a list ans of heights. Each height ans[i] represents the current highest height of any square we have dropped, after dropping squares represented by positions[0], positions[1], ..., positions[i].

Example 1:

Example 2:

Note:

 

  • 1 <= positions.length <= 1000.
  • 1 <= positions[i][0] <= 10^8.
  • 1 <= positions[i][1] <= 10^6.



Idea:

Range query with map

 

Solution:

C++ map

 

C++ vector without merge

C++ / vector with merge (slower)

 

Related Problems:

花花酱 LeetCode 221. Maximal Square

Problem:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

 

Idea:

Dynamic programming



Solution 0: O(n^5)

 

Solution 1: O(n^3)

Solution 2: O(n^2)

 

Solution 1:

 

Solution 2: