执行过程
初始化指针:left=0(高度=1),right=8(高度=7)
before
left=0
right=8
height=[1, 8, 6, 2, 5, 4, 8, 3, 7]
高亮: {"objects": ["ptr:left", "ptr:right"]}
💡 双指针从数组两端开始,宽度最大时先计算面积,然后逐步缩小。
🧠 想象两块板子之间的距离就是容器的宽度,短板决定了能装多少水。
当前 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
高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [0, 8]}}
💡 面积 = 宽度(8) × 较短高度(1)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
更新最大面积!新的最佳面积 = 8
高亮: {"objects": ["ptr:left", "ptr:right"]}
💡 当前的容器比之前找到的都要大,记录下来。
左侧高度(1) < 右侧高度(7),移动左指针(因为短板在左边,移动它才有可能让高度增加)
before
left=0
left_h=1
right_h=7
高亮: {"objects": ["ptr:left"]}
💡 为什么移动更短的一侧?因为面积取决于短板的高度。如果移动长板,宽度减小而短板高度不变,面积只可能更小。移动短板才有机会遇到更高的板。
左指针右移 → left=1
高亮: {"objects": ["ptr:left"]}
当前 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
高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 8]}}
💡 面积 = 宽度(7) × 较短高度(7)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
更新最大面积!新的最佳面积 = 49
高亮: {"objects": ["ptr:left", "ptr:right"]}
💡 当前的容器比之前找到的都要大,记录下来。
右侧高度(7) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)
before
right=8
left_h=8
right_h=7
高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
右指针左移 → right=7
高亮: {"objects": ["ptr:right"]}
当前 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
高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 7]}}
💡 面积 = 宽度(6) × 较短高度(3)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
右侧高度(3) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)
before
right=7
left_h=8
right_h=3
高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
右指针左移 → right=6
高亮: {"objects": ["ptr:right"]}
当前 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
高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 6]}}
💡 面积 = 宽度(5) × 较短高度(8)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
右侧高度(8) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)
before
right=6
left_h=8
right_h=8
高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
右指针左移 → right=5
高亮: {"objects": ["ptr:right"]}
当前 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
高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 5]}}
💡 面积 = 宽度(4) × 较短高度(4)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
右侧高度(4) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)
before
right=5
left_h=8
right_h=4
高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
右指针左移 → right=4
高亮: {"objects": ["ptr:right"]}
当前 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
高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 4]}}
💡 面积 = 宽度(3) × 较短高度(5)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
右侧高度(5) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)
before
right=4
left_h=8
right_h=5
高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
右指针左移 → right=3
高亮: {"objects": ["ptr:right"]}
当前 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
高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 3]}}
💡 面积 = 宽度(2) × 较短高度(2)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
右侧高度(2) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)
before
right=3
left_h=8
right_h=2
高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
右指针左移 → right=2
高亮: {"objects": ["ptr:right"]}
当前 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
高亮: {"objects": ["ptr:left", "ptr:right"], "indices": {"arr:height": [1, 2]}}
💡 面积 = 宽度(1) × 较短高度(6)。任何向内移动都会减少宽度,所以只有移动短板才有可能让高度变大、面积更大。
右侧高度(6) <= 左侧高度(8),移动右指针(因为短板在右边,移动它才有可能让高度增加)
before
right=2
left_h=8
right_h=6
高亮: {"objects": ["ptr:right"]}
💡 同理,面积由短板决定。移动长板不会增加面积上限,所以向内移动短板。
右指针左移 → right=1
高亮: {"objects": ["ptr:right"]}
双指针相遇,结束。最大面积 = 49
🧠 从两端向中间扫描,每次只移动短板,必然不会错过最大面积。