难度: Medium
Submission
运行时间: 40 ms
内存: 0.0 MB
class Solution:
def pourWater(self, heights: List[int], V: int, K: int) -> List[int]:
self.leftStack = []
self.rightStack = []
self.length = len(heights)
self.findLeft(heights, K)
self.findRight(heights, K)
for i in range(V):
if len(self.leftStack) > 0:
low = self.leftStack[-1]
heights[low] += 1
if heights[low] >= heights[low + 1]:
self.leftStack.pop()
if low > 0 and heights[low] >= heights[low - 1]:
self.findLeft(heights, low)
elif len(self.rightStack) > 0:
low = self.rightStack[-1]
heights[low] += 1
if heights[low] >= heights[low - 1]:
self.rightStack.pop()
if low < self.length - 1 and heights[low] >= heights[low + 1]:
self.findRight(heights, low)
else:
heights[K] += 1
self.findLeft(heights, K)
self.findRight(heights, K)
return heights
def findLeft(self, heights, index):
for i in range(index - 1, -1, -1):
if heights[i] < heights[i + 1]:
self.leftStack.append(i)
elif heights[i] > heights[i + 1]:
break
def findRight(self, heights, index):
for i in range(index + 1, self.length):
if heights[i] < heights[i - 1]:
self.rightStack.append(i)
elif heights[i] > heights[i - 1]:
break
Explain
该题解采用了模拟倒水的过程，使用了两个单调栈分别记录倒水过程中左右两侧的可倒水的低洼位置。具体思路如下： 1. 首先利用 findLeft 和 findRight 两个函数分别找出初始位置 K 左右两侧的所有可倒水的低洼位置，并分别存入 leftStack 和 rightStack 中。 2. 开始模拟倒水过程，总共倒 V 次水： - 如果 leftStack 非空，则将水倒在 leftStack 的栈顶位置，并更新该位置的高度。如果该位置已经不再是低洼，则将其从 leftStack 中弹出。然后检查其左侧相邻位置是否因为高度改变而成为新的低洼，如果是则将其加入 leftStack。 - 如果 leftStack 为空但 rightStack 非空，则将水倒在 rightStack 的栈顶位置，并更新该位置的高度。如果该位置已经不再是低洼，则将其从 rightStack 中弹出。然后检查其右侧相邻位置是否因为高度改变而成为新的低洼，如果是则将其加入 rightStack。 - 如果 leftStack 和 rightStack 均为空，则将水倒在初始位置 K 上，并更新 K 位置的高度。然后重新调用 findLeft 和 findRight 函数更新 leftStack 和 rightStack。 3. 倒完 V 次水后，返回更新后的高度数组 heights 即可。
时间复杂度: O(V*n)
空间复杂度: O(n)
class Solution:
def pourWater(self, heights: List[int], V: int, K: int) -> List[int]:
self.leftStack = [] # 记录左侧低洼位置的单调栈
self.rightStack = [] # 记录右侧低洼位置的单调栈
self.length = len(heights) # 高度数组的长度
self.findLeft(heights, K) # 初始查找 K 左侧的低洼位置
self.findRight(heights, K) # 初始查找 K 右侧的低洼位置
for i in range(V): # 倒水 V 次
if len(self.leftStack) > 0: # 如果左侧有低洼位置
low = self.leftStack[-1] # 取左侧最低洼位置
heights[low] += 1 # 将水倒在该位置
if heights[low] >= heights[low + 1]: # 如果该位置已经不再是低洼
self.leftStack.pop() # 将其从左侧低洼栈中弹出
if low > 0 and heights[low] >= heights[low - 1]: # 如果左侧相邻位置成为新的低洼
self.findLeft(heights, low) # 重新查找左侧低洼位置
elif len(self.rightStack) > 0: # 如果右侧有低洼位置
low = self.rightStack[-1] # 取右侧最低洼位置
heights[low] += 1 # 将水倒在该位置
if heights[low] >= heights[low - 1]: # 如果该位置已经不再是低洼
self.rightStack.pop() # 将其从右侧低洼栈中弹出
if low < self.length - 1 and heights[low] >= heights[low + 1]: # 如果右侧相邻位置成为新的低洼
self.findRight(heights, low) # 重新查找右侧低洼位置
else: # 如果左右均无低洼位置
heights[K] += 1 # 将水倒在初始位置 K
self.findLeft(heights, K) # 重新查找 K 左侧的低洼位置
self.findRight(heights, K) # 重新查找 K 右侧的低洼位置
return heights # 返回更新后的高度数组
def findLeft(self, heights, index):
for i in range(index - 1, -1, -1): # 从 index-1 开始向左遍历
if heights[i] < heights[i + 1]: # 如果当前位置是低洼
self.leftStack.append(i) # 将其加入左侧低洼栈
elif heights[i] > heights[i + 1]: # 如果当前位置高于右侧位置
break # 停止遍历
def findRight(self, heights, index):
for i in range(index + 1, self.length): # 从 index+1 开始向右遍历
if heights[i] < heights[i - 1]: # 如果当前位置是低洼
self.rightStack.append(i) # 将其加入右侧低洼栈
elif heights[i] > heights[i - 1]: # 如果当前位置高于左侧位置
break # 停止遍历
Explore
在题解中，如果左右两侧的单调栈均非空时，优先倒水到左侧。这是基于一个常见的倒水模拟原则，即优先填充左侧的低洼位置。这种选择可能是为了模拟自然界中水流由高处向低处流动的趋势，通常左侧的低洼位置在空间位置上更接近倒水初始点的左侧，因此先进行处理。这也可以视为一种设计选择，以保持算法的一致性和可预测性。
当左或右侧的单调栈为空时，若另一侧的栈仍然非空，则会继续在非空的那侧的栈顶位置进行倒水。这保证了水总是被倒在当前可识别的最低洼位置。如果两个栈都为空，水会被倒在初始位置K上。在倒水之后，会重新评估并更新左右两侧的单调栈，确保接下来的倒水仍然是在最低点进行。这种机制确保了倒水操作始终聚焦于当前的最低位置或潜在的新低洼位置。
在每次倒水后，会检查倒水位置的新高度是否还符合低洼位置的条件。如果该位置的高度不再低于其相邻位置，这个位置就会从单调栈中被移除，表示它不再是一个低洼位置。同时，会检查该位置的相邻位置是否因为高度的改变而变成新的低洼地形。如果是，这些新的低洼位置将被加入到相应的单调栈中。这个动态更新过程帮助算法适应复杂的地形变化，并确保始终能够在最低的可用位置进行倒水操作。
当左右均无低洼位置，且水被倒在初始位置K后，会立即调用findLeft和findRight函数重新检查K位置左右两侧是否由于K位置高度的改变而产生新的低洼位置。如果检测到新的低洼位置，这些位置会被加入到相应的单调栈中。这确保了即使在初始位置K周围由于倒水导致地形变化，算法也能及时识别并处理新产生的低洼位置，维持倒水过程的正确性和效率。