1950. 所有子数组最小值中的最大值

Difficulty

Medium

法 1 单调栈

思路

单调栈 1. 首先利用单调栈，计算出每个数作为区间最小值可以往左右两边延拓的长度 2. 用上述求出的延拓长度L,去更新答案数组ans[L - 1]为其对应最小数字集合(延拓长度为L的数字集合)中最大的一个 3. 倒序遍历答案数组,将ans[i]更新max(ans[j]),j >= i

第三步原因解释：如果存在数字N1，N2，他们的延拓范围分别为L1，L2，且有N1 < N2，L1 < L2,那么肯定存在长度为L1的子数组且其最小值为N2(只需要截取长度为L2且最小值为N2的子数组即可),因此需要倒序完成最终的更新

题解


class Solution:
    def findMaximums(self, nums: List[int]) -> List[int]:
        res = [0 for _ in range(len(nums))]
        nums = [-1] + nums + [-1]
        stack = []
        # 找到每一个值 作为最小值的左右边界，即长度
        for i in range(0, len(nums)):
            while stack and nums[i] < nums[stack[-1]]:
                min_val = nums[stack.pop()]
                l = i - stack[-1] - 1
                # print(l, min_val)
                res[l-1] = max(min_val, res[l-1])

            stack.append(i)
        # 这里需要倒序更新，因为 如果 长度为 l+1 的子数组的最小值 是不能大于 长度为 l 的子数组的最小值。后者只需要取前者的 l 长度即可。
        for i in range(len(res)-2, -1, -1):
            res[i] = max(res[i], res[i+1])

        return res