Skip to content

Commit 6654235

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problem: No.0699 (doocs#3328)
No.0699.Falling Squares
1 parent 8228f7c commit 6654235

File tree

4 files changed

+339
-7
lines changed

4 files changed

+339
-7
lines changed

‎solution/0600-0699/0699.Falling Squares/README.md

Lines changed: 113 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -72,12 +72,14 @@ tags:
7272

7373
### 方法一：线段树
7474

75-
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 $log(width)$。更新某个元素的值，只需要更新 $log(width)$ 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用**懒标记**保证效率。
75+
根据题目描述，我们需要维护一个区间集合，支持区间的修改和查询操作。这种情况下，我们可以使用线段树来解决。
76+
77+
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 $\log(width)$，其中 $width$ 是区间的长度。更新某个元素的值，只需要更新 $\log(width)$ 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用**懒标记**保证效率。
7678

7779
- 线段树的每个节点代表一个区间；
78-
- 线段树具有唯一的根节点，代表的区间是整个统计范围，如 $[1, N]$；
80+
- 线段树具有唯一的根节点，代表的区间是整个统计范围，如 $[1, n]$；
7981
- 线段树的每个叶子节点代表一个长度为 1 的元区间 $[x, x]$；
80-
- 对于每个内部节点 $[l, r]$，它的左儿子是 $[l, mid]$，右儿子是 $[mid + 1, r]$, 其中 $mid = ⌊(l + r) / 2⌋$ (即向下取整)。
82+
- 对于每个内部节点 $[l, r]$，它的左儿子是 $[l, mid]$，右儿子是 $[mid + 1, r]$, 其中 $\textit{mid} = \frac{l + r}{2}$；
8183

8284
对于本题，线段树节点维护的信息有：
8385

@@ -86,6 +88,8 @@ tags:
8688

8789
另外，由于数轴范围很大，达到 $10^8$，因此我们采用动态开点。
8890

91+
时间复杂度方面，每次查询和修改的时间复杂度为 $O(\log n)$，总时间复杂度为 $O(n \log n)$。空间复杂度为 $O(n)$。
92+
8993
<!-- tabs:start -->
9094

9195
#### Python3
@@ -388,7 +392,7 @@ func newNode(l, r int) *node {
388392
return &node{
389393
l: l,
390394
r: r,
391-
mid: int(uint(l+r) >> 1),
395+
mid: (l + r) >> 1,
392396
}
393397
}
394398
@@ -474,6 +478,111 @@ func fallingSquares(positions [][]int) []int {
474478
}
475479
```
476480

481+
#### TypeScript
482+
483+
```ts
484+
class Node {
485+
left: Node | null = null;
486+
right: Node | null = null;
487+
l: number;
488+
r: number;
489+
mid: number;
490+
v: number = 0;
491+
add: number = 0;
492+
493+
constructor(l: number, r: number) {
494+
this.l = l;
495+
this.r = r;
496+
this.mid = (l + r) >> 1;
497+
}
498+
}
499+
500+
class SegmentTree {
501+
private root: Node = new Node(1, 1e9);
502+
503+
public modify(l: number, r: number, v: number): void {
504+
this.modifyNode(l, r, v, this.root);
505+
}
506+
507+
private modifyNode(l: number, r: number, v: number, node: Node): void {
508+
if (l > r) {
509+
return;
510+
}
511+
if (node.l >= l && node.r <= r) {
512+
node.v = v;
513+
node.add = v;
514+
return;
515+
}
516+
this.pushdown(node);
517+
if (l <= node.mid) {
518+
this.modifyNode(l, r, v, node.left!);
519+
}
520+
if (r > node.mid) {
521+
this.modifyNode(l, r, v, node.right!);
522+
}
523+
this.pushup(node);
524+
}
525+
526+
public query(l: number, r: number): number {
527+
return this.queryNode(l, r, this.root);
528+
}
529+
530+
private queryNode(l: number, r: number, node: Node): number {
531+
if (l > r) {
532+
return 0;
533+
}
534+
if (node.l >= l && node.r <= r) {
535+
return node.v;
536+
}
537+
this.pushdown(node);
538+
let v = 0;
539+
if (l <= node.mid) {
540+
v = Math.max(v, this.queryNode(l, r, node.left!));
541+
}
542+
if (r > node.mid) {
543+
v = Math.max(v, this.queryNode(l, r, node.right!));
544+
}
545+
return v;
546+
}
547+
548+
private pushup(node: Node): void {
549+
node.v = Math.max(node.left!.v, node.right!.v);
550+
}
551+
552+
private pushdown(node: Node): void {
553+
if (node.left == null) {
554+
node.left = new Node(node.l, node.mid);
555+
}
556+
if (node.right == null) {
557+
node.right = new Node(node.mid + 1, node.r);
558+
}
559+
if (node.add != 0) {
560+
let left = node.left,
561+
right = node.right;
562+
left!.add = node.add;
563+
right!.add = node.add;
564+
left!.v = node.add;
565+
right!.v = node.add;
566+
node.add = 0;
567+
}
568+
}
569+
}
570+
571+
function fallingSquares(positions: number[][]): number[] {
572+
const ans: number[] = [];
573+
const tree = new SegmentTree();
574+
let mx = 0;
575+
for (const [l, w] of positions) {
576+
const r = l + w - 1;
577+
const h = tree.query(l, r) + w;
578+
mx = Math.max(mx, h);
579+
ans.push(mx);
580+
tree.modify(l, r, h);
581+
}
582+
return ans;
583+
}
584+
```
585+
477586
<!-- tabs:end -->
478587

479588
<!-- solution:end -->

‎solution/0600-0699/0699.Falling Squares/README_EN.md

Lines changed: 125 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -68,7 +68,25 @@ Note that square 2 only brushes the right side of square 1, which does not count
6868

6969
<!-- solution:start -->
7070

71-
### Solution 1
71+
### Solution 1: Segment Tree
72+
73+
According to the problem description, we need to maintain a set of intervals that support modification and query operations. In this case, we can use a segment tree to solve the problem.
74+
75+
A segment tree divides the entire interval into multiple non-contiguous sub-intervals, with the number of sub-intervals not exceeding $\log(width)$, where $width$ is the length of the interval. To update the value of an element, we only need to update $\log(width)$ intervals, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, we need to use **lazy propagation** to ensure efficiency.
76+
77+
- Each node of the segment tree represents an interval;
78+
- The segment tree has a unique root node representing the entire statistical range, such as $[1, n]$;
79+
- Each leaf node of the segment tree represents a primitive interval of length 1, $[x, x]$;
80+
- For each internal node $[l, r]$, its left child is $[l, \textit{mid}]$, and its right child is $[\textit{mid} + 1, r]$, where $\textit{mid} = \frac{l + r}{2}$;
81+
82+
For this problem, the information maintained by the segment tree nodes includes:
83+
84+
1. The maximum height $v$ of the blocks in the interval
85+
2. Lazy propagation marker $add$
86+
87+
Additionally, since the range of the number line is very large, up to $10^8$, we use dynamic node creation.
88+
89+
In terms of time complexity, each query and modification has a time complexity of $O(\log n)$, and the total time complexity is $O(n \log n)$. The space complexity is $O(n)$.
7290

7391
<!-- tabs:start -->
7492

@@ -372,7 +390,7 @@ func newNode(l, r int) *node {
372390
return &node{
373391
l: l,
374392
r: r,
375-
mid: int(uint(l+r) >> 1),
393+
mid: (l + r) >> 1,
376394
}
377395
}
378396
@@ -458,6 +476,111 @@ func fallingSquares(positions [][]int) []int {
458476
}
459477
```
460478

479+
#### TypeScript
480+
481+
```ts
482+
class Node {
483+
left: Node | null = null;
484+
right: Node | null = null;
485+
l: number;
486+
r: number;
487+
mid: number;
488+
v: number = 0;
489+
add: number = 0;
490+
491+
constructor(l: number, r: number) {
492+
this.l = l;
493+
this.r = r;
494+
this.mid = (l + r) >> 1;
495+
}
496+
}
497+
498+
class SegmentTree {
499+
private root: Node = new Node(1, 1e9);
500+
501+
public modify(l: number, r: number, v: number): void {
502+
this.modifyNode(l, r, v, this.root);
503+
}
504+
505+
private modifyNode(l: number, r: number, v: number, node: Node): void {
506+
if (l > r) {
507+
return;
508+
}
509+
if (node.l >= l && node.r <= r) {
510+
node.v = v;
511+
node.add = v;
512+
return;
513+
}
514+
this.pushdown(node);
515+
if (l <= node.mid) {
516+
this.modifyNode(l, r, v, node.left!);
517+
}
518+
if (r > node.mid) {
519+
this.modifyNode(l, r, v, node.right!);
520+
}
521+
this.pushup(node);
522+
}
523+
524+
public query(l: number, r: number): number {
525+
return this.queryNode(l, r, this.root);
526+
}
527+
528+
private queryNode(l: number, r: number, node: Node): number {
529+
if (l > r) {
530+
return 0;
531+
}
532+
if (node.l >= l && node.r <= r) {
533+
return node.v;
534+
}
535+
this.pushdown(node);
536+
let v = 0;
537+
if (l <= node.mid) {
538+
v = Math.max(v, this.queryNode(l, r, node.left!));
539+
}
540+
if (r > node.mid) {
541+
v = Math.max(v, this.queryNode(l, r, node.right!));
542+
}
543+
return v;
544+
}
545+
546+
private pushup(node: Node): void {
547+
node.v = Math.max(node.left!.v, node.right!.v);
548+
}
549+
550+
private pushdown(node: Node): void {
551+
if (node.left == null) {
552+
node.left = new Node(node.l, node.mid);
553+
}
554+
if (node.right == null) {
555+
node.right = new Node(node.mid + 1, node.r);
556+
}
557+
if (node.add != 0) {
558+
let left = node.left,
559+
right = node.right;
560+
left!.add = node.add;
561+
right!.add = node.add;
562+
left!.v = node.add;
563+
right!.v = node.add;
564+
node.add = 0;
565+
}
566+
}
567+
}
568+
569+
function fallingSquares(positions: number[][]): number[] {
570+
const ans: number[] = [];
571+
const tree = new SegmentTree();
572+
let mx = 0;
573+
for (const [l, w] of positions) {
574+
const r = l + w - 1;
575+
const h = tree.query(l, r) + w;
576+
mx = Math.max(mx, h);
577+
ans.push(mx);
578+
tree.modify(l, r, h);
579+
}
580+
return ans;
581+
}
582+
```
583+
461584
<!-- tabs:end -->
462585

463586
<!-- solution:end -->

‎solution/0600-0699/0699.Falling Squares/Solution.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ func newNode(l, r int) *node {
99
return &node{
1010
l: l,
1111
r: r,
12-
mid: int(uint(l+r) >> 1),
12+
mid: (l + r) >> 1,
1313
}
1414
}
1515

0 commit comments

Comments
 (0)