755. 倒水
https://leetcode-cn.com/problems/pour-water/
解法一:
注意只有当i-1比i处低的时候,水才能从i向左流入i-1,若相等是不流动的,因此要找到左侧最低处,只能用heights[left-1] <= heights[left]
条件向左搜索(若去掉等号,则只能检测到严格递减的情况,而阶梯平台状的情况会漏掉),而要确定能否流动,要heights[left-1] < heights[left]
条件
class Solution:
def pourWater(self, heights: List[int], V: int, K: int) -> List[int]:
n = len(heights)
for i in range(V):
left = best = K #best记录最佳位置
#先向左找
while left-1 >= 0 and heights[left-1] <= heights[left]:
if heights[left-1] < heights[left]:
best = left-1
left -= 1
if best != K: #若找到
heights[best] += 1
else: #若没找到则向右
right = K
while right+1 < n and heights[right+1] <= heights[right]:
if heights[right+1] < heights[right]:
best = right+1
right += 1
heights[best] += 1
return heights
最后更新于