难度: Hard
Submission
运行时间: 91 ms
内存: 29.5 MB
class Solution(object):
def maximumBeauty(self, flowers):
n = len(flowers)
prefix = [0] * (n + 1)
d_start = {}
d_end = {}
for i in range(n):
if flowers[i] > 0:
prefix[i + 1] = prefix[i] + flowers[i]
else:
prefix[i + 1] = prefix[i]
if flowers[i] in d_start:
d_end[flowers[i]] = i
else:
d_start[flowers[i]] = i
max_ans = - float('inf')
for key in d_start:
if key in d_end:
add_num = prefix[d_end[key] + 1] - prefix[d_start[key]]
if key < 0:
add_num += 2 * key
max_ans = max(max_ans, add_num)
return max_ans
Explain
该题解主要利用了前缀和数组来快速计算区间和，并用字典记录每个值首次出现和最后出现的位置。具体步骤如下：1. 构建一个前缀和数组prefix，记录从开始到当前位置的所有正数的和。2. 使用两个字典d_start和d_end记录每个值首次出现和最后出现的索引。3. 遍历每个在d_start和d_end中出现的值，计算该值的首尾索引区间内的总和，如果是负数，则需要特殊处理（加上两倍的这个负数值），最后更新最大美观度max_ans。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution(object):
def maximumBeauty(self, flowers):
n = len(flowers)
prefix = [0] * (n + 1) # 前缀和数组，用于存储正数的累计和
d_start = {} # 存储每个值首次出现的索引
d_end = {} # 存储每个值最后一次出现的索引
for i in range(n):
if flowers[i] > 0:
prefix[i + 1] = prefix[i] + flowers[i] # 如果是正数，累加到前缀和
else:
prefix[i + 1] = prefix[i] # 如果不是正数，前缀和保持不变
if flowers[i] in d_start:
d_end[flowers[i]] = i # 更新最后出现位置
else:
d_start[flowers[i]] = i # 记录首次出现位置
max_ans = -float('inf') # 初始化最大美观度为负无穷
for key in d_start:
if key in d_end:
add_num = prefix[d_end[key] + 1] - prefix[d_start[key]] # 计算区间和
if key < 0:
add_num += 2 * key # 如果是负数，特殊处理
max_ans = max(max_ans, add_num) # 更新最大美观度
return max_ans
Explore
使用前缀和数组计算区间和的主要优势是其能够在常数时间内求出任意区间的和，从而大大提高了效率。在本题中，我们需要频繁计算特定区间内元素的和，如果每次直接计算，时间复杂度将是O(n)，而如果预先计算好前缀和数组，每次查询的时间复杂度降低到O(1)。这样做特别适合处理大量的区间和查询，能显著减少计算时间，提高整体效率。
字典d_start和d_end分别记录了数组中每个值首次和最后一次出现的位置。对于重复出现的值，这种方法只记录首次和最后一次出现的位置，因此能够准确计算出该值在整个数组中的贡献范围。这种处理逻辑是合理的，并不会影响最终的美观度计算，因为我们关注的是从首次到最后一次出现的范围内的所有元素的总和，与这个值在中间重复出现的次数无关。
在计算区间和时对负数进行特殊处理是为了反映出负数对美观度的负面影响。计算时加上两倍负数值的逻辑是因为这个负数既影响了首次出现的位置的美观值，也影响了最后出现的位置的美观值。通过这样的处理，实际上是从总和中减去了两次该负数的值，更准确地反映了该区间的实际美观度贡献。此处理方式确保计算的美观度结果更符合实际情况，考虑到了负数对整体美观的双重负面效果。