算法训练营day50(补)，单调栈2
// 503. 下一个更大元素 II
func nextGreaterElements(nums []int) []int {
n := len(nums)
result := make([]int, n)
for i := 0; i < n; i++ {
result[i] = -1
}
stack := make([]int, 0)
//因为收尾相连，采用i%2运算实现循环
for i := 0; i < 2*n; i++ {
j := i % n
for len(stack) > 0 && nums[j] > nums[stack[len(stack)-1]] {
index := stack[len(stack)-1]
stack = stack[:len(stack)-1]
result[index] = nums[j]
}
stack = append(stack, j)
}
return result
}
//42. 接雨水
func trap(height []int) int {
n := len(height)
stack := make([]int, 1, n)
sum := 0
for i := 1; i < n; i++ {
if height[i] == height[stack[len(stack)-1]] {
stack = stack[:len(stack)-1]
} else {
for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
mid := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack) > 0 {
//求高度
h := min(height[i], height[stack[len(stack)-1]]) - height[mid]
//求宽度
w := i - stack[len(stack)-1] - 1
//求总面积
sum += (h * w)
}
}
}
stack = append(stack, i)
}
return sum
}
func min(a, b int) int {
if a < b {
return a
}
return b
}