难度: Hard
Submission
运行时间: 280 ms
内存: 24.9 MB
class Solution:
def maxProfit(self, prices: List[int], profits: List[int]) -> int:
n = len(prices)
'''
二分单调栈
num,t
10 8
9 7
保证num越大时，t越大
'''
dp = [-1] * (n)
# 第一次二分单调栈
up = []
for i in range(n):
a,b = prices[i], profits[i]
pos = bisect_right(up,(a,0))
if pos:
dp[i] = up[pos-1][1] + b
if not pos:
while pos < len(up) and up[pos][1] <= b:
del up[pos]
up.insert(0,(a,b))
else:
if up[pos-1][1] < b:
while pos < len(up) and up[pos][1] <= b:
del up[pos]
up.insert(pos,(a,b))
# 第二次单调栈，以dp值作为num
res = -1
up = []
for i in range(n):
a,b = prices[i], profits[i]
pos = bisect_right(up,(a,0))
if pos:
res = max(res,up[pos-1][1] + b)
if dp[i] == -1:
continue
if not pos:
while pos < len(up) and up[pos][1] <= dp[i]:
del up[pos]
up.insert(0,(a,dp[i]))
else:
if up[pos-1][1] < dp[i]:
while pos < len(up) and up[pos][1] <= dp[i]:
del up[pos]
up.insert(pos,(a,dp[i]))
# print(dp)
return res
Explain
该题解采用了二分单调栈的方法来求解价格递增的最大利润三元组问题。首先，我们使用一个单调栈来维护一个由价格和利润组成的元组列表，确保随着价格的增加，相应的利润也是单调递增的。在遍历价格和利润数组时，我们尝试通过二分查找的方式找到当前价格能插入单调栈的位置，并根据这个位置更新可能的最大利润（通过之前的利润加上当前的利润）。第二次使用单调栈时，我们将DP值作为新的利润，以此来尝试更新最终的最大利润。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def maxProfit(self, prices: List[int], profits: List[int]) -> int:
n = len(prices)
# 初始化DP数组，用于存储中间结果
dp = [-1] * (n)
# 第一次构建单调栈
up = []
# 遍历每个元素，尝试更新DP值
for i in range(n):
a, b = prices[i], profits[i]
pos = bisect_right(up, (a, 0))
if pos:
dp[i] = up[pos-1][1] + b
# 维护单调栈，确保满足条件
if not pos or up[pos-1][1] < b:
while pos < len(up) and up[pos][1] <= b:
del up[pos]
up.insert(pos, (a, b))
# 第二次构建单调栈，以DP值作为新的利润
res = -1
up = []
for i in range(n):
a, b = prices[i], profits[i]
if dp[i] == -1:
continue
pos = bisect_right(up, (a, 0))
if pos:
res = max(res, up[pos-1][1] + b)
# 维护单调栈，确保满足条件
if not pos or up[pos-1][1] < dp[i]:
while pos < len(up) and up[pos][1] <= dp[i]:
del up[pos]
up.insert(pos, (a, dp[i]))
# 返回最大利润
return res
Explore
单调栈是一种特殊的栈结构，其中的元素按照单调递增或单调递减的顺序排列。在这个问题中，单调栈用于维护一个元组列表，其中每个元组包含一个价格和一个利润。这样，随着价格的增加，利润也保持递增。在这个场景中，单调栈帮助我们快速找到对于当前价格来说，之前可以获得的最高利润，从而计算当前组合的总利润，并进一步尝试更新最大利润。
在单调栈中使用二分查找是为了快速找到一个位置，使得新元素可以插入而不破坏栈的单调性。这种策略有效地减少了插入操作的时间复杂度，从O(n)降低到O(log n)，因此在需要频繁插入且关心性能的场景中非常有用。然而，这种策略前提是栈内的元素按某种可比较的顺序排列，如果元素间没有明确的比较规则或者栈的更新操作非常频繁而且复杂，则可能不适用。
题解中第一次构建单调栈是基于初始的价格和利润，目的是为了计算每个位置可能得到的最大利润并存储到DP数组中。第二次构建单调栈时，使用DP数组中的元素作为新的利润，这是因为DP值代表了考虑之前所有可能选择后的最大利润。这样，第二次构建单调栈时，我们实际上在尝试基于之前已经计算好的最优解来更新可能的更高利润，从而找到整个问题的最终最大利润。
在维护单调栈时，如果新插入的元素（价格，利润）的利润比栈中某些元素的利润高，那么这些元素将不再有助于未来的最大利润计算，因为我们总可以选择新元素而获得更高的利润。因此，删除操作是为了保持栈的单调递增性质，确保每个元素都是对应价格下可能获得的最大利润，从而在每次查询时都能得到正确和最优的结果。