盛最多水的容器 (0011_container_with_most_water)

标签: two_pointers, greedy · 难度: MEDIUM

输入

height:
1
8
6
2
5
4
8
3
7

执行过程

Step 1 · pointer_init
初始化指针:left=0(高度=1),right=8(高度=7)

before

left=0 right=8 height=[1, 8, 6, 2, 5, 4, 8, 3, 7]

after

高亮: {"objects": ["ptr:left", "ptr:right"]}
💡 双指针从数组两端开始,宽度最大时先计算面积,然后逐步缩小。
🧠 想象两块板子之间的距离就是容器的宽度,短板决定了能装多少水。
Step 2 · area_compute
当前 left=0(高度=1),right=8(高度=7),宽度=8,较短高度=1,面积=8

before

left=0 right=8 left_h=1 right_h=7 width=8 height_min=1 area=8 best=0

after

高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [0, 8]}}
💡 面积 = 宽度(8) × 较短高度(1)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
Step 3 · best_update
更新最大面积!新的最佳面积 = 8

before

after

best=8
高亮: {"objects": ["ptr:left", "ptr:right"]}
💡 当前的容器比之前找到的都要大,记录下来。
Step 4 · comparison_reason
左侧高度(1) < 右侧高度(7),移动左指针(因为短板在左边,移动它才有可能让高度增加)

before

left=0 left_h=1 right_h=7

after

高亮: {"objects": ["ptr:left"]}
💡 为什么移动更短的一侧?因为面积取决于短板的高度。如果移动长板,宽度减小而短板高度不变,面积只可能更小。移动短板才有机会遇到更高的板。
Step 5 · pointer_move
左指针右移 → left=1

before

after

left=1 right=8
高亮: {"objects": ["ptr:left"]}
Step 6 · area_compute
当前 left=1(高度=8),right=8(高度=7),宽度=7,较短高度=7,面积=49

before

left=1 right=8 left_h=8 right_h=7 width=7 height_min=7 area=49 best=8

after

高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 8]}}
💡 面积 = 宽度(7) × 较短高度(7)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
Step 7 · best_update
更新最大面积!新的最佳面积 = 49

before

after

best=49
高亮: {"objects": ["ptr:left", "ptr:right"]}
💡 当前的容器比之前找到的都要大,记录下来。
Step 8 · comparison_reason
右侧高度(7) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)

before

right=8 left_h=8 right_h=7

after

高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
Step 9 · pointer_move
右指针左移 → right=7

before

after

left=1 right=7
高亮: {"objects": ["ptr:right"]}
Step 10 · area_compute
当前 left=1(高度=8),right=7(高度=3),宽度=6,较短高度=3,面积=18

before

left=1 right=7 left_h=8 right_h=3 width=6 height_min=3 area=18 best=49

after

高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 7]}}
💡 面积 = 宽度(6) × 较短高度(3)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
Step 11 · comparison_reason
右侧高度(3) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)

before

right=7 left_h=8 right_h=3

after

高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
Step 12 · pointer_move
右指针左移 → right=6

before

after

left=1 right=6
高亮: {"objects": ["ptr:right"]}
Step 13 · area_compute
当前 left=1(高度=8),right=6(高度=8),宽度=5,较短高度=8,面积=40

before

left=1 right=6 left_h=8 right_h=8 width=5 height_min=8 area=40 best=49

after

高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 6]}}
💡 面积 = 宽度(5) × 较短高度(8)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
Step 14 · comparison_reason
右侧高度(8) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)

before

right=6 left_h=8 right_h=8

after

高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
Step 15 · pointer_move
右指针左移 → right=5

before

after

left=1 right=5
高亮: {"objects": ["ptr:right"]}
Step 16 · area_compute
当前 left=1(高度=8),right=5(高度=4),宽度=4,较短高度=4,面积=16

before

left=1 right=5 left_h=8 right_h=4 width=4 height_min=4 area=16 best=49

after

高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 5]}}
💡 面积 = 宽度(4) × 较短高度(4)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
Step 17 · comparison_reason
右侧高度(4) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)

before

right=5 left_h=8 right_h=4

after

高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
Step 18 · pointer_move
右指针左移 → right=4

before

after

left=1 right=4
高亮: {"objects": ["ptr:right"]}
Step 19 · area_compute
当前 left=1(高度=8),right=4(高度=5),宽度=3,较短高度=5,面积=15

before

left=1 right=4 left_h=8 right_h=5 width=3 height_min=5 area=15 best=49

after

高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 4]}}
💡 面积 = 宽度(3) × 较短高度(5)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
Step 20 · comparison_reason
右侧高度(5) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)

before

right=4 left_h=8 right_h=5

after

高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
Step 21 · pointer_move
右指针左移 → right=3

before

after

left=1 right=3
高亮: {"objects": ["ptr:right"]}
Step 22 · area_compute
当前 left=1(高度=8),right=3(高度=2),宽度=2,较短高度=2,面积=4

before

left=1 right=3 left_h=8 right_h=2 width=2 height_min=2 area=4 best=49

after

高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 3]}}
💡 面积 = 宽度(2) × 较短高度(2)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
Step 23 · comparison_reason
右侧高度(2) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)

before

right=3 left_h=8 right_h=2

after

高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
Step 24 · pointer_move
右指针左移 → right=2

before

after

left=1 right=2
高亮: {"objects": ["ptr:right"]}
Step 25 · area_compute
当前 left=1(高度=8),right=2(高度=6),宽度=1,较短高度=6,面积=6

before

left=1 right=2 left_h=8 right_h=6 width=1 height_min=6 area=6 best=49

after

高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 2]}}
💡 面积 = 宽度(1) × 较短高度(6)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
Step 26 · comparison_reason
右侧高度(6) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)

before

right=2 left_h=8 right_h=6

after

高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
Step 27 · pointer_move
右指针左移 → right=1

before

after

left=1 right=1
高亮: {"objects": ["ptr:right"]}
Step 28 · return
双指针相遇,结束。最大面积 = 49

before

after

result=49
🧠 从两端向中间扫描,每次只移动短板,必然不会错过最大面积。