2021-12-26：给定一个长度为n的数组arr，求有多少个子数组满足 : 子数组两端的值，是这个子数组的最小值和次小值，最小值和次小值谁在最左和最右无所谓。 n＜=100000（10^5） n*

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代码

2021-12-26：给定一个长度为n的数组arr，求有多少个子数组满足 : 子数组两端的值，是这个子数组的最小值和次小值，最小值和次小值谁在最左和最右无所谓。 n＜=100000（10^5） n*的相关教程结束。