这种前几大的题通通用partition就可以在O(N)时间内解决，之所以要特意写个题解是因为想把partition的算法记下来，每次写都写得很纠结

程序看着比较奇怪，因为我是找的前k大，然后再找前k大里面最小的，之所以这样是为了复用之前 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/ 的函数

type pair struct {v intp int}func maxProfit(k int, prices []int) int {n := len(prices)stack := make([]pair, n)profits := make([]int, 0, n)v := 0p := -1top := 0for true {for v = p + 1; v+1 < n && prices[v] >= prices[v+1]; v++ {}for p = v; p+1 < n && prices[p] <= prices[p+1]; p++ {}//fmt.Println(v,p)if v == p {break}/*case 1, do nothing but pop the last vp pair and put them into the profit array/for top > 0 && prices[v] <= prices[stack[top-1].v] {profits = append(profits, prices[stack[top-1].p]-prices[stack[top-1].v])top--}/case 2, merge the two vp pairs*/for top > 0 && prices[p] >= prices[stack[top-1].p] {profits = append(profits, prices[stack[top-1].p]-prices[v])v = stack[top-1].vtop--}stack[top] = pair{v: v, p: p}top++}for top > 0 {profits = append(profits, prices[stack[top-1].p]-prices[stack[top-1].v])top--}ans := 0//fmt.Println(profits)if len(profits) <= k {ans = accumulate(profits)return ans}ans = accumulate(firstKLargest(profits, k))return ans}func accumulate(arr []int) int{n := len(arr)ans := 0for i := 0; i < n; i++ {ans += arr[i]}return ans}func firstKLargest(slice []int, k int) []int {length := len(slice)if length <= k {    return slice}m := slice[rand.Intn(length)]less := make([]int, 0, length)more := make([]int, 0, length)equal := make([]int, 0, length)for _, item := range slice {    switch {    case item < m:        less = append(less, item)    case item > m:        more = append(more, item)    default :        equal = append(equal, item)    }}if len(more) > k {    return firstKLargest(more, k)} else if len(more) == k {    return more}else if len(more) + len(equal) >= k{    more = append(more, equal[:k-len(more)]...)    //fmt.Println("debug more",more)    return more}more = append(more, equal...)// fmt.Println("Less", less)// fmt.Println("More", more)// fmt.Println("Equal", equal)part := firstKLargest(less, k-len(more))return append(part, more...)}复制代码