42 接雨水
代码如下
func trap(height []int) int {
if len(height) <= 2 { 首先需要形成一个凹槽才能接到雨水，而凹槽需要至少三个元素，所以如果长度小于等于2就直接返回0
return 0
}
res := 0
stack := make([]int,len(height)) 定义一个单调递增栈，栈底元素为最大值
for i := 0 ; i < len(height) ; i++ { 遍历数组
for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] { 如果当前遍历元素大于栈顶元素则说明可能形成了凹槽
mid := height[stack[len(stack)-1]] 此时栈顶元素就为凹槽的中间的那个元素，而当前遍历的元素是凹槽的右边元素，而栈顶下一个元素则为左边的元素
stack = stack[:len(stack)-1] 弹出栈顶元素
if len(stack) != 0 { 此时需要判断当弹出栈顶元素后，栈里面是否还有元素，如果没有元素，则说明没有左边一个元素，依然无法形成凹槽，但是如果栈不为空，则说明可以形成凹槽
h := min(height[i],height[stack[len(stack)-1]])-mid 高即为当前遍历元素和栈顶元素，此时因为已经弹出了一个元素，所以此时的栈顶元素就为左边的元素 ，在减去中间元素的高度即为可接雨水的高度
w := i - stack[len(stack)-1] - 1 宽度是两者之间的距离
res += h * w 对结果进行累加
}
}
stack = append(stack,i) 如果不大于那么就进行入栈操作
}
return res
}
func min(a,b int) int {
if a < b {
return a
}else {
return b
}
}
84 柱状图中最大的矩形
代码如下
func largestRectangleArea(heights []int) int {
res := 0
heights = append([]int{0},heights...) //在数组的头尾加0
heights = append(heights,0)
stack := make([]int,len(heights))
for i := 0 ; i < len(heights) ; i++ {
for len(stack) > 0 && heights[i] < heights[stack[len(stack)-1]] { 为递减的单调栈，所以如果栈顶元素大于当前元素需要进行计算
mid := stack[len(stack)-1] 取出栈顶元素作为中间元素即为计算基准即高 ，此时当前遍历元素为他的右边元素，比他小。而他在栈里的下一个元素也比他小
stack = stack[:len(stack)-1]
left := stack[len(stack)-1]
tmp :=heights[mid]*(i-left-1) 右边下标减去左边下标在减1 即为距离
if tmp > res { 取一个最大值
res = tmp
}
}
stack = append(stack,i)
}
return res
}
