Hot-100-Algorithm/双指针/接雨水/main.go

package main

import (
	"fmt"
)

func main() {
	resule := trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})
	fmt.Println("最大接水数为：", resule)
}

func trap(height []int) int {
	value := 0
	leftmax := make([]int, len(height))
	rightmax := make([]int, len(height))
	leftmax[0] = height[0]
	rightmax[len(height)-1] = height[len(height)-1]
	for i := 1; i < len(height); i++ {
		leftmax[i] = max(leftmax[i-1], height[i])
	}
	for j := len(height) - 2; j >= 0; j-- {
		rightmax[j] = max(rightmax[j+1], height[j])
	}
	fmt.Println(leftmax)
	fmt.Println(rightmax)
	for i := 0; i < len(height); i++ {
		value += min(leftmax[i], rightmax[i]) - height[i]
	}

	return value
}

// 错误思路:只计算凹槽，一个桶里可能有多个凹槽
//
//func trap(height []int) int {
//	tap := make([]int, 0)
//	for i := 0; i < len(height); i++ {
//		if i-1 >= 0 && i+1 < len(height) {
//			if height[i-1]-height[i] > 0 && height[i] < height[i+1] {
//				tap = append(tap, i)
//			}
//		}
//	}
//	fmt.Println(tap)
//	value := 0
//	for i := range tap {
//		tempvalue := 0
//		left, right := tap[i], tap[i]
//		for height[left-1] > height[left] {
//			left--
//		}
//		for height[right+1] > height[right] {
//			right++
//		}
//		fmt.Println("左右指针指向：", left, right)
//		temp := min(height[left], height[right])
//		for left != right {
//			if temp-height[left] < 0 {
//				left++
//			} else {
//				value += temp - height[left]
//				tempvalue += temp - height[left]
//				fmt.Println("当前temp和left的值", temp, height[left])
//				fmt.Println("添加体积：", tempvalue)
//
//				left++
//			}
//
//		}
//		fmt.Println("临时体积：", tempvalue)
//	}
//	return value
//}