从Leetcode 每日一题练习继续讨论：
1937. 扣分后的最大得分
1937. Maximum Number of Points with Cost
题解
本题每一行中各个位置能得到的最大点数仅与上一行有关, 因此只要解决两行矩阵第二行如何根据第一行求得每个位置能得到的最大点数这一子问题即可得解. 最直接的想法当然是暴力, 对第二行每个数字都遍历第一行的全部数字, 每个数字都通过点数-距离得到其对于第二行该数字的价值. 最后取价值最大的数加在该数字上, 这种方式如果每行数字个数为n个, 需要n^2的复杂度. 则若共有m行, 整体需要m*n^2的复杂度. 因此我们需要思考一些方式使得每行只需遍历常数次即能让下一行每个位置找到上一行中的最大值. 这个问题的思路在某些地方与"接雨水"这到经典题有相似之处. 虽然我们在从左向右遍历的时候对于任意位置不能得到全局最大值, 但在遍历的过程中其实已经获得了当前下标左侧的全部值的信息, 因此我们可以记录到某一下标的左侧数组中的全部数字到这一下标的最大价值, 只需定义一个变量leftmax, 并在遍历过程中不断将leftmax-1和当前下标的数字比较并更新leftmax. 举例来说, 如1,3,2,6,4这几个数字, 遍历1时leftmax为1, 遍历3时将leftmax-1(1-1)和3比较得到新的leftmax为3, 遍历2时将leftmax-1(3-1)和2比较得到新的leftmax为2. 将每个位置的leftmax都保存下来, 这样相当于将求每个位置的最大价值这一问题拆为两个子问题, 即求解每个位置左侧的最大价值和每个位置右侧的最大价值. 最后再将这两个问题的解比较即得最终解. 这样的好处在于这两个子问题都是可以"并行求解"的, 即对行r遍历一遍行r-1即可求出所有位置的一个子问题的解, 求得两个子问题的解也只需两次. 而原问题则需要每个位置都遍历一遍行r-1, 在遍历的过程中虽然访问了行r-1的全部数字, 但大部分信息都被抛弃了, 在下一个位置又要重新获取这些信息. 这是非常低效的, 在之前题解中多次强调, 能越充分的利用信息就有越高的求解效率.
因此本题求解过程为对行r, 遍历两次行r-1获得全部位置的leftmax和rightmax, 最后遍历一遍行r并更新每个位置的最大价值即可.
代码
func maxPoints(points [][]int) int64 {
rows := len(points)
if rows == 1{
return int64(maxSlice(points[0]))
}
cols := len(points[0])
leftmax := make([]int, cols)
rightmax := make([]int, cols)
for row:=1;row<rows;row++{
leftmaxnow := points[row-1][0]
for index,num := range points[row-1]{
leftmax[index] = max(leftmaxnow-1, num)
leftmaxnow = leftmax[index]
}
rightmaxnow := points[row-1][cols-1]
for index:=cols-1;index>=0;index--{
rightmax[index] = max(rightmaxnow-1, points[row-1][index])
rightmaxnow = rightmax[index]
}
for col:=0;col<cols;col++{
points[row][col] += max(leftmax[col],rightmax[col])
}
}
return int64(maxSlice(points[rows-1]))
}
func maxSlice(numbers []int) int {
maxNum := numbers[0]
for _, num := range numbers[1:] {
if num > maxNum {
maxNum = num
}
}
return maxNum
}