• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 4小时前 2次浏览

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)		
    }
}

程序员灯塔
转载请注明原文链接:b_zj_小于左边且大于右边的所有数(单调栈)
喜欢 (0)