699 Falling Squares 掉落的方塊
Description:
There are several squares being dropped onto the X-axis of a 2D plane.
You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the ith square with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti.
Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands on the top side of another square or on the X-axis. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.
After each square is dropped, you must record the height of the current tallest stack of squares.
Return an integer array ans where ans[i] represents the height described above after dropping the ith square.
Example:
Example 1:
Input: positions = [[1,2],[2,3],[6,1]]
Output: [2,5,5]
Explanation:
After the first drop, the tallest stack is square 1 with a height of 2.
After the second drop, the tallest stack is squares 1 and 2 with a height of 5.
After the third drop, the tallest stack is still squares 1 and 2 with a height of 5.
Thus, we return an answer of [2, 5, 5].
Example 2:
Input: positions = [[100,100],[200,100]]
Output: [100,100]
Explanation:
After the first drop, the tallest stack is square 1 with a height of 100.
After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100.
Thus, we return an answer of [100, 100].
Note that square 2 only brushes the right side of square 1, which does not count as landing on it.
Constraints:
1 <= positions.length <= 1000
1 <= lefti <= 10^8
1 <= sideLengthi <= 10^6
題目描述:
在無限長的數(shù)軸（即 x 軸）上仲翎，我們根據(jù)給定的順序放置對應(yīng)的正方形方塊。
第 i 個掉落的方塊（positions[i] = (left, side_length)）是正方形柬批，其中 left 表示該方塊最左邊的點位置(positions[i][0])喷楣，side_length 表示該方塊的邊長(positions[i][1])。
每個方塊的底部邊緣平行于數(shù)軸（即 x 軸），并且從一個比目前所有的落地方塊更高的高度掉落而下蜒谤。在上一個方塊結(jié)束掉落，并保持靜止后至扰，才開始掉落新方塊鳍徽。
方塊的底邊具有非常大的粘性，并將保持固定在它們所接觸的任何長度表面上（無論是數(shù)軸還是其他方塊）敢课。鄰接掉落的邊不會過早地粘合在一起阶祭，因為只有底邊才具有粘性。
返回一個堆疊高度列表 ans 直秆。每一個堆疊高度 ans[i] 表示在通過 positions[0], positions[1], ..., positions[i] 表示的方塊掉落結(jié)束后濒募，目前所有已經(jīng)落穩(wěn)的方塊堆疊的最高高度。
示例 :
示例 1:
輸入: [[1, 2], [2, 3], [6, 1]]
輸出: [2, 5, 5]
解釋:
第一個方塊 positions[0] = [1, 2] 掉落：
_aa
_aa
-------
方塊最大高度為 2 圾结。
第二個方塊 positions[1] = [2, 3] 掉落：
__aaa
__aaa
__aaa
_aa__
_aa__
--------------
方塊最大高度為5瑰剃。
大的方塊保持在較小的方塊的頂部，不論它的重心在哪里筝野，因為方塊的底部邊緣有非常大的粘性晌姚。
第三個方塊 positions[1] = [6, 1] 掉落：
__aaa
__aaa
__aaa
_aa
_aa___a
--------------
方塊最大高度為5。
因此歇竟，我們返回結(jié)果[2, 5, 5]挥唠。
示例 2:
輸入: [[100, 100], [200, 100]]
輸出: [100, 100]
解釋: 相鄰的方塊不會過早地卡住，只有它們的底部邊緣才能粘在表面上焕议。
注意:
1 <= positions.length <= 1000.
1 <= positions[i][0] <= 10^8.
1 <= positions[i][1] <= 10^6.
思路:
- 模擬
由于數(shù)據(jù)量不大
可以采用直接模擬
每次掉落一個方塊, 更新它后面的所有方塊的高度, 因為前面的掉落不會影響到后面的方塊, 這樣做是沒問題的
時間復(fù)雜度為 O(n ^ 2), 空間復(fù)雜度為 O(n) - 線段樹
這個題本質(zhì)上還是區(qū)間更新及查詢的問題
方塊都是連續(xù)的, 不過不需要對區(qū)間中間的進行操作, 所以可以將坐標離散化
用 TreeMap 記錄左右邊界 [left, left + size - 1]
時間復(fù)雜度為 O(nlgn), 空間復(fù)雜度為 O(n)
代碼:
C++:
class Solution
{
private:
int a[10005], mark[10005];
void build(int p, int l, int r)
{
if (l == r)
{
mark[p] = a[p] = 0;
return;
}
int mid = l + (r - l >> 1);
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
a[p] = max(a[p << 1], a[p << 1 | 1]);
}
void push_down(int p)
{
mark[p << 1] = max(mark[p], mark[p << 1]);
mark[p << 1 | 1] = max(mark[p], mark[p << 1 | 1]);
a[p << 1] = max(a[p << 1], mark[p << 1]);
a[p << 1 | 1] = max(a[p << 1 | 1], mark[p << 1 | 1]);
mark[p] = 0;
}
int query(int p, int l, int r, int ql, int qr)
{
if (qr < l or ql > r) return 0;
else if (ql <= l and qr >= r) return a[p];
else
{
if (mark[p]) push_down(p);
int mid = l + (r - l >> 1);
if (qr <= mid) return query(p << 1, l, mid, ql, qr);
else if (ql > mid) return query(p << 1 | 1, mid + 1, r, ql, qr);
else return max(query(p << 1, l, mid, ql, qr),query(p << 1 | 1, mid + 1, r, ql, qr));
}
}
void update(int p, int l, int r, int ul, int ur, int val)
{
if (ur < l or ul > r) return;
else if (ul <= l and ur >= r)
{
a[p] = max(a[p], val);
mark[p] = max(mark[p], val);
}
else
{
if (mark[p]) push_down(p);
int mid = l + (r - l >> 1);
update(p << 1, l, mid, ul, ur, val);
update(p << 1 | 1, mid + 1, r, ul, ur, val);
a[p] = max(a[p << 1], a[p << 1 | 1]);
}
}
public:
vector<int> fallingSquares(vector<vector<int>>& positions)
{
vector<int> pos;
for (auto &p : positions)
{
pos.push_back(p.front());
pos.push_back(p.front() + p.back() - 1);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
int n = pos.size(), height = 0;
unordered_map<int, int> m;
for (int i = 0; i < n; ++i) m[pos[i]] = i;
build(1, 0, n - 1);
vector<int> result;
for (auto &p : positions)
{
int ql = m[p.front()], qr = m[p.front() + p.back() - 1];
int h = query(1, 0, n - 1, ql, qr);
height = max(height, h + p.back());
result.push_back(height);
update(1, 0, n - 1, ql, qr, h + p.back());
}
return result;
}
};
Java:
class Solution {
public List<Integer> fallingSquares(int[][] positions) {
List<Integer> result = new ArrayList<>();
int n = positions.length;
int[] squares = new int[n];
for (int i = 0; i < n; i++) {
int left1 = positions[i][0], height1 = positions[i][1], right1 = positions[i][0] + positions[i][1];
squares[i] += height1;
for (int j = i + 1; j < n; j++) {
int left2 = positions[j][0], height2 = positions[j][1], right2 = positions[j][0] + positions[j][1];
if (left2 < right1 && left1 < right2) squares[j] = Math.max(squares[i], squares[j]);
}
}
for (int s : squares) result.add(result.isEmpty() ? s : Math.max(result.get(result.size() - 1), s));
return result;
}
}
Python:
class Solution:
def fallingSquares(self, positions: List[List[int]]) -> List[int]:
squares, result = [0] * (n := len(positions)), []
for i, (left, size) in enumerate(positions):
right = left + size
squares[i] += size
for j in range(i + 1, n):
left2, size2 = positions[j]
right2 = left2 + size2
if left2 < right and left < right2:
squares[j] = max(squares[j], squares[i])
for s in squares:
result.append(max(result[-1], s) if result else s)
return result
