这种前几大的题通通用partition就可以在O(N)时间内解决，之所以要特意写个题解是因为想把partition的算法记下来，每次写都写得很纠结
程序看着比较奇怪，因为我是找的前k大，然后再找前k大里面最小的，之所以这样是为了复用之前
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/
的函数
type pair struct {
v int
p int
}
func maxProfit(k int, prices []int) int {
n := len(prices)
stack := make([]pair, n)
profits := make([]int, 0, n)
v := 0
p := -1
top := 0
for 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].v
top--
}
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 := 0
for 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...)
}
