难度: Medium
Submission
运行时间: 218 ms
内存: 32.2 MB
class Solution:
def minCost(self, nums: List[int], costs: List[int]) -> int:
minStk, maxStk = [], []
dp = [inf] * len(nums)
dp[0] = 0
for i, (num, cost) in enumerate(zip(nums, costs)):
while maxStk and nums[maxStk[-1]] <= num:
k = maxStk.pop()
dp[i] = min(dp[i], cost + dp[k])
maxStk.append(i)
while minStk and nums[minStk[-1]] > num:
k = minStk.pop()
dp[i] = min(dp[i], cost + dp[k])
minStk.append(i)
return dp[-1]
Explain
题解使用了动态规划和单调栈的结合来解决问题。动态规划数组 `dp[i]` 代表从起点到达点 `i` 的最小成本。解决思路是遍历每一个位置 `i`，并维护两个单调栈：`maxStk` 和 `minStk`。`maxStk` 维护一个单调递减的栈，其中 `nums` 的值是递减的；当遇到一个比栈顶更大的元素时，我们从栈顶移除元素，并更新 `dp[i]`。类似地，`minStk` 维护一个单调递增的栈，用于处理当前元素比栈顶元素小的情况。通过这种方式，我们能够在遍历数组的同时，快速找到之前的位置 `k`，使得从 `k` 到 `i` 的转移成本最小，即 `dp[i] = min(dp[i], dp[k] + cost[i])`。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def minCost(self, nums: List[int], costs: List[int]) -> int:
# 初始化两个单调栈和dp数组
minStk, maxStk = [], []
dp = [float('inf')] * len(nums)
dp[0] = 0 # 起始点的成本为0
# 遍历每个元素
for i, (num, cost) in enumerate(zip(nums, costs)):
# 维护maxStk，确保其元素对应的nums值单调递减
while maxStk and nums[maxStk[-1]] <= num:
k = maxStk.pop()
dp[i] = min(dp[i], cost + dp[k]) # 更新dp值
maxStk.append(i)
# 维护minStk，确保其元素对应的nums值单调递增
while minStk and nums[minStk[-1]] > num:
k = minStk.pop()
dp[i] = min(dp[i], cost + dp[k]) # 更新dp值
minStk.append(i)
return dp[-1] # 返回最后一个位置的最小成本
Explore
单独使用动态规划来解决此类问题时，我们通常需要对每个位置i考虑所有可能的前驱位置k，这样的时间复杂度会达到O(n^2)，对于大数据量的情况下计算量过大。单调栈的使用可以帮助我们在O(n)的时间复杂度内通过维护一个有序的结构，快速找到满足条件的前驱位置k，从而有效地优化状态转移方程的求解过程。此外，单调栈可以帮助我们在遍历数组的同时，维护当前元素左侧的一个有序序列，这种方法比使用其他数据结构如堆或二叉搜索树在此问题中更为直接和高效。
单调栈通过维护一个单调的元素序列，使得每次计算dp[i]时，我们只需要考虑栈中的有限几个元素而不是全部历史元素。例如，单调递减栈确保了栈中任何一个位置j的nums[j]都大于栈顶位置k的nums[k]，这意味着对于任何非栈顶元素，一旦新的元素比栈顶大或相等，栈顶元素就不再有可能是最优选择，可被移除。这种机制减少了不必要的比较和计算，使得每个元素平均只被处理一次，从而将时间复杂度从O(n^2)降低到O(n)。
同时维护单调递增栈和单调递减栈可以让我们根据不同的条件快速找到最优的前驱位置。单调递减栈用于找到所有nums值大于当前元素的最近位置，这有助于我们在计算成本时采用更大的nums值作为基准。相反，单调递增栈帮助我们找到nums值小于当前元素的最近位置，这在某些情况下可能提供更小的转移成本。每个栈的维护保证了在每个位置i的计算中，我们总是能够快速找到最优的前驱k，从而更新dp[i] = min(dp[i], cost + dp[k])，确保了算法的高效性和正确性。