难度: Medium
Submission
运行时间: 120 ms
内存: 37.5 MB
class Solution:
def maxScore(self, prices: List[int]) -> int:
# for any index i, j
# prices[i] - prices[j] = i - j
# i.e. prices[i] - i = prices[j] - j
d = {}
for i, p in enumerate(prices):
diff = p - i
d[diff] = d.get(diff, 0) + p
return max(d.values())
Explain
这道题解的核心思路是基于转换后的差值来归类和计算得分。具体来说，对于数组中的每个元素 prices[i]，我们计算出 p - i 的差值（即 prices[i] - i），这个差值用作字典 d 的键。这个字典 d 的值是该差值对应所有 prices[i] 的总和。算法的关键在于，如果两个价格的差值相等，即 prices[i] - i == prices[j] - j，那么这两个位置可以构成一对有效的组合。我们通过字典记录下每个差值的总和，最后返回字典中最大的值，即为最大线性股票得分。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxScore(self, prices: List[int]) -> int:
# 初始化字典，用于存储每个差值的总和
d = {}
# 遍历价格数组
for i, p in enumerate(prices):
# 计算当前索引和价格的差值
diff = p - i
# 如果差值已存在，则更新其总和；否则，设置初始总和为当前价格
d[diff] = d.get(diff, 0) + p
# 返回所有差值总和中的最大值，即为最大线性股票得分
return max(d.values())
Explore
在这个算法中，使用差值 `prices[i] - i` 作为字典的键是为了识别可以构成有效组合的价格元素。这种处理方法的特别之处在于它能够将问题简化为查找具有相同差值的元素。如果两个元素的 `prices[i] - i` 相同，意味着这两个元素的价格差额对于其在数组中的位置差是相等的。这样的处理使得算法可以通过简单地累加具有相同差值的价格来快速计算得分，从而提高了效率。通过这种方式，我们能够将时间复杂度控制在线性水平，即 O(n)，这在处理大数据集时尤为重要。
在这个题目的上下文中，`有效组合`指的是两个不同的数组索引 i 和 j，其中 `prices[i] - i` 等于 `prices[j] - j`。这种组合意味着两者的价格和位置差的关系是相同的，这在某些特定的问题设定中可能有特殊意义。例如，在股票交易分析中，这可能代表在不同时间点的相同价格调整。具体到这道题目，这样的组合有助于我们通过累加这些价格来找到可能的最大得分。算法通过识别所有具有相同价格位置差值的元素，并将他们的价格累加起来，从而尝试找到可能的最大总和，这个总和即为题目所求的最大线性股票得分。
是的，根据算法的逻辑，所有具有相同差值 `prices[i] - i` 的元素都被视为等效，并将其价格累加以计算得分。这种方法的一个潜在问题是它忽略了元素之间的位置信息。具体来说，尽管两个价格具有相同的差值，它们在数组中的实际位置可能相距很远。这种情况下，仅仅因为差值相同就将它们视为等效可能会在某些应用场景中引入误差。此外，这种方法也假设了所有的价格都是正的或者处理方式能够适应不同的价格范围，如果存在负价格或者极端的价格波动，可能需要对算法进行调整以适应这些特殊情况。