题解 | #数据分析#

由于我们只需要考虑每个长度为N的子数组的最大值,因此我们枚举每个元素,记录其可以为子数组最大值的覆盖区间长度,在该区间内该元素始终为最大值；同时我们可以知道,若存在一个长度为m的子数组最大值为k,显然可以找到任意一个长度小于等于m的子数组使其最大值为k；因此我们首先通过单调栈求出每个元素的覆盖区间,同时倒序遍历子数组长度,并将当前符合长度的区间存入小顶堆,依次记录答案即可.
时间复杂度：O(nlogn)

import heapq
import collections
class Solution:
    def getMinimums(self , numbers ):
        n = len(numbers)
        left_,right_ = [1 for i in range(n)],[1 for i in range(n)]
        stack = []
        for i in range(len(numbers)):
            if not stack:
                stack.append([i,numbers[i]])
            else:
                if stack[-1][1] >= numbers[i]:
                    stack.append([i,numbers[i]])
                else:
                    while stack and stack[-1][1] < numbers[i]:
                          right_[stack[-1][0]] += i - 1 - stack[-1][0]
                          stack.pop(-1)
                    stack.append([i,numbers[i]])

        if stack:
            for i in range(len(stack) - 1):
                right_[stack[i][0]] += stack[-1][0] - stack[i][0]
        stack.clear()

        for i in range(len(numbers) - 1,-1,-1):
            if not stack:
                stack.append([i,numbers[i]])
            else:
                if stack[-1][1] >= numbers[i]:
                    stack.append([i,numbers[i]])
                else:
                    while stack and stack[-1][1] < numbers[i]:
                          left_[stack[-1][0]] +=  stack[-1][0] - i - 1
                          stack.pop(-1)
                    stack.append([i,numbers[i]])

        if stack:
            for i in range(len(stack) - 1):
                left_[stack[i][0]] += stack[i][0] - stack[-1][0]
        cnt = collections.defaultdict(list)
        for i in range(len(left_)):
             cnt[left_[i] + right_[i] - 1].append(numbers[i])
        v = []
        for k in cnt:
            for m in cnt[k]:
                v.append([k,m])
        v.sort(key = lambda x:-x[0])
        l = 0
        heap = []

        ans = [0] * n

        # 倒序遍历保证了任意时刻堆中区间均符合我们需要的子数组长度
        for i in range(n,0,-1):
            while l < len(v) and v[l][0] >= i:
                heapq.heappush(heap, v[l][1])
                l += 1
            ans[i - 1] = heap[0]
        return ans