204 lines
4.6 KiB
Go
204 lines
4.6 KiB
Go
package main
|
||
|
||
import "fmt"
|
||
|
||
func main() {
|
||
fmt.Println(maxSlidingWindow([]int{7, 2, 4}, 2))
|
||
}
|
||
func maxSlidingWindow(nums []int, k int) []int {
|
||
if k > len(nums) {
|
||
return []int(nil)
|
||
}
|
||
numlist := make([]int, 0, k)
|
||
result := make([]int, 0)
|
||
|
||
for i := 0; i < len(nums); i++ {
|
||
if len(numlist) == 0 {
|
||
numlist = append(numlist, i)
|
||
if i >= k-1 {
|
||
result = append(result, nums[numlist[0]])
|
||
}
|
||
continue
|
||
}
|
||
if numlist[0] <= i-k {
|
||
numlist = numlist[1:]
|
||
}
|
||
p := len(numlist) - 1
|
||
//fmt.Println(numlist)
|
||
for {
|
||
if len(numlist) == 0 || p < 0 {
|
||
break
|
||
}
|
||
if nums[numlist[p]] < nums[i] {
|
||
p--
|
||
} else {
|
||
break
|
||
}
|
||
}
|
||
numlist = numlist[:p+1]
|
||
if len(numlist) < k {
|
||
numlist = append(numlist, i)
|
||
} else {
|
||
numlist = append(numlist[1:], i)
|
||
}
|
||
if i >= k-1 {
|
||
result = append(result, nums[numlist[0]])
|
||
}
|
||
}
|
||
//fmt.Println("result", result)
|
||
return result
|
||
}
|
||
|
||
//func maxSlidingWindow(nums []int, k int) []int {
|
||
// queue := make([]int, k)
|
||
// result := make([]int, 0)
|
||
// for i := 0; i < k; i++ {
|
||
// queue[i] = nums[i]
|
||
// }
|
||
// maxnum := 0
|
||
// for i := 0; i < len(nums)-k+1; i++ {
|
||
// if i == 0 {
|
||
// queuetmp := make([]int, len(queue))
|
||
// copy(queuetmp, queue) // 深拷贝
|
||
// sort.Ints(queuetmp)
|
||
// maxnum = queuetmp[k-1]
|
||
// result = append(result, queuetmp[k-1])
|
||
//
|
||
// //fmt.Println("result:", result)
|
||
// continue
|
||
// }
|
||
// fmt.Println("queue分割前：", queue)
|
||
// queueA := queue[1:]
|
||
// //fmt.Println("queueA", queueA)
|
||
// queueA = append(queueA, nums[i+k-1])
|
||
// queue = queueA
|
||
// fmt.Println("max", maxnum)
|
||
// fmt.Println("当前右边界:", nums[i+k-1])
|
||
// if nums[i+k-1] >= maxnum {
|
||
// maxnum = nums[i+k-1]
|
||
// result = append(result, nums[i+k-1])
|
||
// } else {
|
||
// queuetmp := make([]int, len(queue))
|
||
// copy(queuetmp, queue) // 深拷贝
|
||
// sort.Ints(queuetmp)
|
||
// result = append(result, queuetmp[k-1])
|
||
// }
|
||
// //
|
||
//
|
||
// //fmt.Println("queueA2", queueA)
|
||
// //fmt.Println("queueA", queue)
|
||
//
|
||
// fmt.Println("result:", result)
|
||
// }
|
||
// return result
|
||
//}
|
||
|
||
//func maxSlidingWindow(nums []int, k int) []int {
|
||
// queue := make([]int, k)
|
||
// result := make([]int, 0)
|
||
// for i := 0; i < k; i++ {
|
||
// queue[i] = nums[i]
|
||
// }
|
||
// maxnum := 0
|
||
// for i := 0; i < len(nums)-k+1; i++ {
|
||
// if i == 0 {
|
||
// queuetmp := make([]int, len(queue))
|
||
// copy(queuetmp, queue) // 深拷贝
|
||
// sort.Ints(queuetmp)
|
||
// maxnum = queuetmp[k-1]
|
||
// result = append(result, queuetmp[k-1])
|
||
//
|
||
// //fmt.Println("result:", result)
|
||
// continue
|
||
// }
|
||
// fmt.Println("queue分割前：", queue)
|
||
// queueA := queue[1:]
|
||
// //fmt.Println("queueA", queueA)
|
||
// queueA = append(queueA, nums[i+k-1])
|
||
// queue = queueA
|
||
// fmt.Println("max", maxnum)
|
||
// fmt.Println("当前右边界:", nums[i+k-1])
|
||
// if nums[i+k-1] >= maxnum {
|
||
// maxnum = nums[i+k-1]
|
||
// result = append(result, nums[i+k-1])
|
||
// } else {
|
||
// queuetmp := make([]int, len(queue))
|
||
// copy(queuetmp, queue) // 深拷贝
|
||
// sort.Ints(queuetmp)
|
||
// result = append(result, queuetmp[k-1])
|
||
// }
|
||
// //
|
||
//
|
||
// //fmt.Println("queueA2", queueA)
|
||
// //fmt.Println("queueA", queue)
|
||
//
|
||
// fmt.Println("result:", result)
|
||
// }
|
||
// return result
|
||
//}
|
||
|
||
//func maxSlidingWindow(nums []int, k int) []int {
|
||
// queue := make([]int, k)
|
||
// result := make([]int, 0)
|
||
// for i := 0; i < k; i++ {
|
||
// queue[i] = nums[i]
|
||
// }
|
||
// maxnum := 0
|
||
// for i := 0; i < len(nums)-k+1; i++ {
|
||
// if i == 0 {
|
||
// queuetmp := make([]int, len(queue))
|
||
// copy(queuetmp, queue) // 深拷贝
|
||
// sort.Ints(queuetmp)
|
||
// maxnum = queuetmp[k-1]
|
||
// result = append(result, queuetmp[k-1])
|
||
//
|
||
// //fmt.Println("result:", result)
|
||
// continue
|
||
// }
|
||
// fmt.Println("queue分割前：", queue)
|
||
// queueA := queue[1:]
|
||
// //fmt.Println("queueA", queueA)
|
||
// queueA = append(queueA, nums[i+k-1])
|
||
// queue = queueA
|
||
// fmt.Println("max", maxnum)
|
||
// fmt.Println("当前右边界:", nums[i+k-1])
|
||
// if nums[i+k-1] >= maxnum {
|
||
// maxnum = nums[i+k-1]
|
||
// result = append(result, nums[i+k-1])
|
||
// } else {
|
||
// queuetmp := make([]int, len(queue))
|
||
// copy(queuetmp, queue) // 深拷贝
|
||
// sort.Ints(queuetmp)
|
||
// result = append(result, queuetmp[k-1])
|
||
// }
|
||
// //
|
||
//
|
||
// //fmt.Println("queueA2", queueA)
|
||
// //fmt.Println("queueA", queue)
|
||
//
|
||
// fmt.Println("result:", result)
|
||
// }
|
||
// return result
|
||
//}
|
||
|
||
//func maxSlidingWindow(nums []int, k int) []int {
|
||
// result := make([]int, 0)
|
||
// nowmax := 0
|
||
// for i := 0; i < len(nums)-k+1; i++ {
|
||
// if i == 0 {
|
||
// tmp := nums[:k]
|
||
// sort.Ints(tmp)
|
||
// result = append(result, tmp[k-1])
|
||
// nowmax = tmp[k-1]
|
||
// continue
|
||
// }
|
||
// if nums[i+k-1] > nowmax {
|
||
// result = append(result, nums[i+k-1])
|
||
// } else {
|
||
// result = append(result, nowmax)
|
||
// }
|
||
//
|
||
// }
|
||
// return result
|
||
//}
|