2021-05-30：数组的元素个数一定大于2,请问两个不相邻元素的和的最大值是多少？

福大大架构师每日一题 · CSDN · · 2020-01-01 00:00

福大大答案2021-05-30：

top4问题，求前4个最大值的问题。大根堆和小根堆都可以，代码采用的是小根堆。求完top4，双重遍历，当序号不相邻的时候，求出两个数的和，取最大值。这个最大值就是需要返回的值。时间复杂度是O(N)。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
)

func main() {

    a := NewTop4()
    ret := a.getMaxTwoSum1([]int{2, 4, 2, 1})
    fmt.Println(ret)

}

type Top4 struct {
    //小根堆
    heap     []*Node
    heapSize int
}

func NewTop4() *Top4 {
    ret := &Top4{}
    ret.heap = make([]*Node, 4)
    return ret
}

func (this *Top4) getMaxTwoSum1(arr []int) int {
    for i := 0; i < len(arr); i++ {
        curNode := &Node{Val: arr[i], Index: i}
        //小根堆
        if this.heapSize == len(this.heap) {
            if this.compare(curNode, this.heap[0]) {
                //不用管了
                continue
            }
            curNode, this.heap[0] = this.heap[0], curNode
            this.HeapDown(0)
        } else {
            this.Push(curNode)
        }
    }

    ans := math.MinInt64
    for i := 0; i < this.heapSize-1; i++ {
        for j := i + 1; j < this.heapSize; j++ {
            if this.heap[i].Index-this.heap[j].Index != 1 && this.heap[i].Index-this.heap[j].Index != -1 {
                ans = this.getMax(ans, this.heap[i].Val+this.heap[j].Val)
            }
        }
    }

    return ans
}
func (this *Top4) getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

type Node struct {
    Val   int
    Index int
}

//索引上移，小根堆
func (this *Top4) HeapUp(index int) {
    for (index-1)/2 != index && !this.compare(this.heap[(index-1)/2], this.heap[index]) { //父节点小于当前节点，当前节点必须上移
        this.heap[index], this.heap[(index-1)/2] = this.heap[(index-1)/2], this.heap[index]
        //加强堆
        //this.nodeIndexMap[this.heap[index]], this.nodeIndexMap[this.heap[(index-1)/2]] = (index-1)/2, index
        index = (index - 1) / 2
    }
}

//索引下沉，小根堆
func (this *Top4) HeapDown(index int) {
    left := 2*index + 1
    for left <= this.heapSize-1 { //左孩子存在
        //获取小孩子
        largest := left
        if left+1 <= this.heapSize-1 && this.compare(this.heap[left+1], this.heap[left]) {
            largest++
        }

        //比较
        if !this.compare(this.heap[index], this.heap[largest]) { //当前大于最小孩子，必须下沉
            this.heap[index], this.heap[largest] = this.heap[largest], this.heap[index]
            //加强堆
            //this.nodeIndexMap[this.heap[index]], this.nodeIndexMap[this.heap[largest]] = largest, index
        } else {
            break
        }

        //下一次遍历
        index = largest
        left = 2*index + 1
    }
}

func (this *Top4) Push(node *Node) {
    this.heap[this.heapSize] = node
    //加强堆
    //this.nodeIndexMap[node] = this.heapSize
    //索引上移
    this.HeapUp(this.heapSize)
    this.heapSize++
}

func (this *Top4) Pop() *Node {
    ans := this.heap[0]
    this.heap[0], this.heap[this.heapSize-1] = this.heap[this.heapSize-1], this.heap[0]
    //加强堆
    //this.nodeIndexMap[this.heap[0]] = 0
    //this.nodeIndexMap[this.heap[this.heapSize-1]] = -1

    this.heapSize--
    //索引下沉
    this.HeapDown(0)
    return ans
}

func (this *Top4) compare(node1 *Node, node2 *Node) bool {
    return node1.Val < node2.Val
}

执行结果如下：

原文地址：访问原文地址
快照地址：访问文章快照

分享到微博