2021-12-26：给定一个长度为n的数组arr，求有多少个子数
原创2021-12-26：给定一个长度为n的数组arr，求有多少个子数
原创
福大大架构师每日一题
发布于 2021-12-26 23:23:08
发布于 2021-12-26 23:23:08
2021-12-26：给定一个长度为n的数组arr，求有多少个子数组满足 :
子数组两端的值，是这个子数组的最小值和次小值，最小值和次小值谁在最左和最右无所谓。
n<=100000（10^5） n*logn O(N)。
来自腾讯。
答案2021-12-26：
单调栈。从左往右一次单调栈，从右往左一次单调栈。
时间复杂度：O(N)。
额外空间复杂度：O(N)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := []int{1, 2, 3, 2, 1}
ret := nums(arr)
fmt.Println(ret)
}
func nums(arr []int) int {
if len(arr) < 2 {
return 0
}
n := len(arr)
values := make([]int, n)
times := make([]int, n)
size := 0
ans := 0
for i := 0; i < len(arr); i++ {
for size != 0 && values[size-1] > arr[i] {
size--
ans += times[size] + cn2(times[size])
}
if size != 0 && values[size-1] == arr[i] {
times[size-1]++
} else {
values[size] = arr[i]
times[size] = 1
size++
}
}
for size != 0 {
size--
ans += cn2(times[size])
}
for i := len(arr) - 1; i >= 0; i-- {
for size != 0 && values[size-1] > arr[i] {
size--
ans += times[size]
}
if size != 0 && values[size-1] == arr[i] {
times[size-1]++
} else {
values[size] = arr[i]
times[size] = 1
size++
}
}
return ans
}
func cn2(n int) int {
return (n * (n - 1)) >> 1
}执行结果如下：
图片
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读