LeetCode 42. 接雨水 Golang 解法,双指针,单调栈
原题链接
困难
作者:
lkm
,
2021-12-13 21:04:26
,
所有人可见
,
阅读 235
// 单调栈解法,栈中存一个类似阶梯的东西
func trap(height []int) int {
var stack []int
var res int
n := len(height)
stack = append(stack, 0)
for i := 1; i < n; i++ {
if len(stack) == 0 || height[i] <= height[stack[len(stack)-1]] {
stack = append(stack, i)
} else {
for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
//出栈
currI := stack[len(stack)-1]
stack = stack[0 : len(stack)-1]
if len(stack) > 0 {
h := min(height[i], height[stack[len(stack)-1]])
res += ((h - height[currI]) * (i - stack[len(stack)-1] - 1))
}
}
stack = append(stack, i)
}
}
return res
}
//双指针
func trap2(height []int) int {
l, r := 0, len(height)-1
maxL, maxR := height[l], height[r]
res := 0
for l < r {
if maxL > maxR {
res += maxR - height[r]
r--
maxR = max(height[r], maxR)
} else {
res += maxL - height[l]
l++
maxL = max(height[l], maxL)
}
}
return res
}
func min(x, y int) int {
if x > y {
return y
}
return x
}
func max(x, y int) int {
if x > y {
return x
}
return y
}