推荐观看方法:二、三和四
以下是疑问的地方
height [ left - 1] 是可能成为 max_left 的变量, 同理,height [ right + 1 ] 是可能成为
right_max 的变量。 只要保证 height [ left - 1 ] < height [ right + 1 ] ,那么
max_left 就一定小于 max_right。
对应下面这个代码块:
这个解法的核心思想是双指针法。为了理解这个方法,我们首先要明白一个事实:对于某个柱子来说,它能够接的雨水量取决于它左边的最高柱子和右边的最高柱子中的较小者,减去该柱子的高度。
现在,我们来看这个解法的逻辑:
初始化两个指针 left
和 right
,分别指向数组的第二个位置和倒数第二个位置。这是因为最左边和最右边的柱子不可能接雨水,所以我们从第二个柱子开始考虑。
初始化两个变量 max_left
和 max_right
来分别记录 left
指针左边的最高柱子和 right
指针右边的最高柱子。
遍历数组中的每个柱子。对于每个柱子,我们都检查 height[left-1]
和 height[right+1]
。这两个值是当前柱子左边和右边的柱子的高度。
如果 height[left-1] < height[right+1]
,这意味着 left
指针左边的柱子比 right
指针右边的柱子矮。因此,max_left
有可能被 height[left-1]
更新(如果 height[left-1]
比 max_left
大的话)。
这里的关键是,由于 height[left-1]
比 height[right+1]
小,所以 max_left
一定小于或等于 max_right
。这是因为 max_right
是由 height[right+1]
或更大的值更新的。
如果 height[left-1]
大于或等于 height[right+1]
,我们就更新 right
指针和 max_right
。
对于每个柱子,我们都计算它能接的雨水量,并将其加到总和中。
这个方法的关键在于,我们每次都移动 left
或 right
指针中指向较矮柱子的那个。这确保了 max_left
和 max_right
总是代表当前柱子左边和右边的最高柱子。
你提到了一个很好的问题。让我们更深入地探讨这个问题。
首先,我们要明确一点:在每一步中,我们都是在移动left
或right
中指向较矮柱子的那个。这意味着,如果height[left-1] < height[right+1]
,那么left
指针会向右移动,而right
指针不会移动。
现在,考虑以下两种情况:
height[left-1]
大于max_left
:在这种情况下,max_left
会被height[left-1]
更新。但是,由于height[left-1]
仍然小于height[right+1]
,所以max_left
(即使被更新后)仍然小于或等于max_right
。
height[left-1]
小于或等于max_left
:在这种情况下,max_left
不会被更新,它的值保持不变。由于之前的步骤已经确保了max_left
小于或等于max_right
,所以这个关系仍然成立。
因此,无论height[left-1]
的值如何,我们都可以确保max_left
始终小于或等于max_right
,只要height[left-1] < height[right+1]
这个条件成立。
这种方法的关键在于,我们始终移动指向较矮柱子的指针,这确保了我们总是在考虑当前柱子左边和右边的最高柱子。