难度: Medium
Submission
运行时间: 204 ms
内存: 33.2 MB
class Solution:
def findMaximums(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [-1]*n
right = [n] * n
ans = [-1] * n
st = []
for i in range(n):
while st and nums[st[-1]] > nums[i]:
cur = st.pop()
right[cur] = i
if st: left[i] = st[-1]
st.append(i)
# st = []
# for i in range(n-1,-1,-1):
# while st and nums[st[-1]] > nums[i]:
# cur = st.pop()
# left[cur] = i
# st.append(i)
for i,(l,r) in enumerate(zip(left,right)):
ans[r-l-2] = max(ans[r-l-2],nums[i])
for i in range(n-2,-1,-1):
ans[i] = max(ans[i],ans[i+1])
return ans
Explain
此题解采用单调栈和动态规划的思想来寻找所有子数组的最小值中的最大值。首先，使用单调栈来确定每个元素作为最小值可以扩展到的最左和最右边界。数组left和right分别存储每个元素作为最小值时，左边和右边的边界索引。接着，利用这些边界信息，计算每个可能的子数组长度（从1到n）中的最小值的最大值，并存储在数组ans中。最后，从后向前遍历数组ans，确保每一个长度的最小值的最大值是正确的（即长度为k的所有子数组的最小值的最大值，不会小于长度为k+1的对应值）。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findMaximums(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [-1]*n # 存储每个元素作为最小值时，左边界索引
right = [n] * n # 存储每个元素作为最小值时，右边界索引
ans = [-1] * n # 存储每种长度子数组的最小值中的最大值
st = [] # 单调递增栈
for i in range(n):
while st and nums[st[-1]] > nums[i]:
cur = st.pop()
right[cur] = i # 更新右边界
if st: left[i] = st[-1] # 更新左边界
st.append(i)
for i,(l,r) in enumerate(zip(left,right)):
ans[r-l-2] = max(ans[r-l-2],nums[i]) # 更新ans数组
for i in range(n-2,-1,-1):
ans[i] = max(ans[i],ans[i+1]) # 确保ans数组的正确性
return ans
Explore
使用单调递增栈的目的是为了在数组中维护一个非递增的元素序列。当遇到一个新元素比栈顶元素小，即打破了递增趋势时，栈顶元素的右边界自然就确定为当前元素的索引。这样可以确保每个元素作为最小值时，其能扩展的最大范围被正确记录。如果使用单调递减栈，栈中的元素将按递减顺序排列，这样无法直接找到作为最小值时的最大右边界，因此不适用于本问题。
在算法中，通过逐个检查数组元素并更新栈来确保边界的正确性。对于每个元素，当它导致栈顶元素出栈时，就会更新那些元素的右边界为当前元素的索引。同时，当前元素的左边界则是栈中前一个元素的索引。这种方式确保了每个元素作为最小值时的左右边界只会被设定一次，从而避免了漏判或重复判定的情况。
在更新ans数组时使用的索引`r-l-2`是基于左右边界的定义计算出子数组的长度。由于左右边界是不包含在子数组中的，所以实际子数组的长度为`r - l - 1`。但由于数组索引是从0开始的，对应的长度为`k`的子数组在ans中的索引应为`k-1`，因此使用`r-l-2`来更新ans数组。这样的计算确保每个子数组长度的最小值能被正确地归类和更新。
反向遍历ans数组并更新其值的目的是确保较短长度的子数组的最小值不会被较长长度的子数组的最小值所覆盖。因为在正向填充ans数组时，可能仅考虑了局部最优解，没有考虑全局最优解，即可能存在某些长子数组的最小值实际上小于某些短子数组的最小值。因此，通过反向遍历并更新，我们确保每个长度为k的子数组的最小值至少不小于长度为k+1的子数组的最小值，从而维持整体的一致性和正确性。