b_zj_小于左边且大于右边的所有数(单调栈)

RT
input: 9,8,7,3,4,2,1
output: 9,8,7,2,1

思路

package main
import (
    "fmt"
    "math"
)
func solve(A []int) []int {
    st := []int{}
    minLeft := math.MaxInt32
    for _, x := range A {
        if x < minLeft { //小于左边的最小值就小于左边全部
            st = append(st, x)
            minLeft = x
        } else { //x > minLeft 则说明左边有数不符合【大于右边所有数】的条件,即不大于x
            for len(st) > 0 && st[len(st)-1] < x {
                st = st[0:len(st)-1]
            }
        }
    }
    return st
}
func main() {
    A := []int{9,8,7,3,4,2,1}
    ans := solve(A)
    for _, x := range ans {
        fmt.Printf("%d ", x)		
    }
}
上一篇:NOIP 模拟 $30\; \rm 毛二琛$


下一篇:让文字和标签的大小随着屏幕的尺寸做变化 等比缩放js