算法:
接雨水的题目在leetcode上面出现了两次,不过解法却很不相同,一类是简单的双指针使用场景;一类是栈的典型实用。
这类题目的关键在于对题目的理解,以及拆解成简单的问题。
题目1:
算法:核心在于读懂题目
描述转换成:min(h[i],h[j])*(j-1)的最大值,有了这个之后很容易想到双指针
1. 偏移的策略是,h[i]和h[j]谁小,偏移谁,
2. 因为从上面的公式来看,只有min(h[i],h[j])变大才有可能让乘积变大。
题目2:
题目分析:
我们发现这种蓄水情况,需要先找到最高点,然后分别计算两边的蓄水情况,求和即可。
先找到数组里面最高的位置,然后从两边往中间靠拢,分别计算两边的数据之和。
1. 高1<高2:从左往右,第一个高的入栈,后续比他小或等于的计算数值,求和;
2. 高1==高2:从左往右,算法同1
3. 高1=0: 不入栈,不做计算;// 最左边
题目1:
https://leetcode-cn.com/problems/container-with-most-water/
代码实现:
func maxArea(height []int) int {
if height == nil {
return 0
}
i,j := 0,len(height)-1
sum := 0
for i<j {
h := height[i]
w := j-i
// 移动高度小的那个位置
if height[i] > height[j] {
h = height[j]
j--
} else {
i++
}
tmp := h*w
if tmp > sum {
sum = tmp
}
}
return sum
}
// 算法:核心在于读懂题目
// 描述转换成:min(h[i],h[j])*(j-1)的最大值
// 有了这个之后很容易想到双指针
// 偏移的策略是,h[i]和h[j]谁小,偏移谁,
// 因为从上面的公式来看,只有min(h[i],h[j])变大才有可能让乘积变大。
执行结果:
题目2:
https://leetcode-cn.com/problems/trapping-rain-water/
代码实现:
/*算法:
先找到数组里面最高的位置,然后从两边往中间靠拢,分别计算两边的数据之和。
1.高1<高2:从左往右,第一个高的入栈,后续比他小或等于的计算数值,求和;
2.高1==高2:从左往右,算法同1
3.高1=0: 不入栈,不做计算;// 最左边
*/
func trap(height []int) int {
// step 1: 找到数组的最高点
top := getTopIndx(height)
// step 2: 计算左半部分的蓄水和
sum := Sum(height[:top])
// step 3: 计算右半部分的蓄水和,这里是从右往左的排序,原因是蓄水池的对称性
var rights []int
for i:= len(height)-1; i>top; i--{
rights = append(rights,height[i])
}
sum += Sum(rights)
return sum
}
func getTopIndx(arr []int) int{
if len(arr) == 0 {
return 0
}
max:= arr[0]
top := 0
for idx,v :=range arr {
if max < v {
max = v
top = idx
}
}
return top
}
func Sum(arr []int) int {
if len(arr) == 0 {
return 0
}
var sum int
var max int = arr[0]
for _,v:= range arr {
if max < v {
max = v
continue
}
sum += max - v
}
return sum
}