LeetCode 42. 接雨水

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 42. 接雨水

思路分析

要计算接雨水的量，可以使用双指针的方法。具体步骤如下：

初始化指针和变量：使用两个指针 left 和 right 分别指向数组的两端，同时维护两个变量 leftMax 和 rightMax 来记录当前左右两边的最大高度。

移动指针：在每一步中，比较 leftMax 和 rightMax。

如果 leftMax 小于 rightMax，则移动 left 指针，并计算当前位置的雨水量（leftMax - height[left]）。

如果 rightMax 小于等于 leftMax，则移动 right 指针，并计算当前位置的雨水量（rightMax - height[right]）。

累加雨水量：将每一步计算的雨水量累加到总量中。

参考代码

func trap(height []int) int {
	left, right := 0, len(height)-1
	leftMax, rightMax := 0, 0
	res := 0

	for left < right {
		if height[left] < height[right] {
			if height[left] >= leftMax {
				leftMax = height[left]
			} else {
				res += leftMax - height[left]
			}
			left++
		} else {
			if height[right] >= rightMax {
				rightMax = height[right]
			} else {
				res += rightMax - height[right]
			}
			right--
		}
	}
	return res
}

时间复杂度：O(n)，遍历一次数组。

空间复杂度：O(1)，只使用了常数空间。

func trap(height []int) int {
	n := len(height)
	if n <= 2 {
		return 0
	}

	res := 0
	leftMax := make([]int, n)
	leftMax[0] = height[0]
	for i := 1; i < n; i++ {
		leftMax[i] = max(leftMax[i-1], height[i])
	}

	rightMax := make([]int, n)
	rightMax[n-1] = height[n-1]
	for i := n - 2; i >= 0; i-- {
		rightMax[i] = max(rightMax[i+1], height[i])
	}

	for i := 1; i < n-1; i++ {
		minHeight := min(leftMax[i], rightMax[i])
		res += max(0, minHeight-height[i])
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/96961914