2021-12-26：给定一个长度为n的数组arr，求有多少个子数组满足 : 子数组两端的值

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
}

执行结果如下：

左神java代码