题解 | #愤怒的小鸟#

package main

import "fmt"

func main() {
	// n
	var n int
	fmt.Scan(&n)
	// 高度数组
	var h = make([]int, n)
	for i := 0; i < n; i++ {
		var temp int
		fmt.Scan(&temp)
		h[i] = temp
	}
	left := make([]int, n)
	right := make([]int, n)
	for i := 0; i < n; i++ {
		left[i] = -1
		right[i] = -1
	}
	stack := make([]int, 10^6)
	top := 0
	for i := 0; i < n; i++ {
		for top > 0 && h[stack[top-1]] <= h[i] {
			right[stack[top-1]] = i
			top--
		}
		stack[top] = i
		top++
	}
	top = 0
	for i := n - 1; i >= 0; i-- {
		for top > 0 && h[stack[top-1]] <= h[i] {
			left[stack[top-1]] = i
			top--
		}
		stack[top] = i
		top++
	}
	v := make([]int, n+1)
	for i := 0; i < n; i++ {
		if left[i] != -1 {
			v[1]++
			v[left[i]+2]--
		}
		if right[i] != -1 {
			v[right[i]+1]++
		}
	}
	for i := 1; i <= n; i++ {
		v[i] += v[i-1]
	}
	//输出res
	for i := 1; i <= n; i++ {
		fmt.Printf("%d ", v[i])
	}
}

我只能说，我很生气，为什么golang总是超时，牛客网官方能不能修一修，我寻思我的解答过程也没啥问题啊，*。

这题第一次解出来但是超时了，没有用到差分的思想，就是根据单调栈算出左右第一个不大于目标值的元素下标，然后逐个遍历计算，确实很耗时间。

看了解析，妙啊，加上差分，然后兴冲冲使用了差分来算，***还是超时，我不能接受，看有没有大佬看一下了