Python3(3.9) 解法, 执行用时: 1317ms, 内存消耗: 15444K, 提交时间: 2020-11-24 09:55:33

#
# 找到所有长度子数组中最大值的最小值
# @param numbers int整型一维数组 牛牛给出的数据
# @return int整型一维数组
#
import sys 
class Solution:
    def getMinimums(self , numbers ):
        # write code here
        n = len(numbers)
        right = [n] * n 
        left = [-1] * n 
        st = []
        ans = [sys.maxsize] * n 
        for i in range(n):
            while st and numbers[st[-1]] < numbers[i]:
                right[st[-1]] = i 
                st.pop()
            if st:
                left[i] = st[-1]
            st.append(i)
        for i in range(n):
            length = right[i] - left[i] - 1
            ans[length-1] = min(ans[length-1],numbers[i])
        for i in range(n-2,-1,-1):
            ans[i] = min(ans[i],ans[i+1])
        return ans

C++(clang++11) 解法, 执行用时: 949ms, 内存消耗: 4700K, 提交时间: 2020-11-23 12:44:27

class Solution {
public:
    /**
     * 找到所有长度子数组中最大值的最小值
     * @param numbers int整型vector 牛牛给出的数据
     * @return int整型vector
     */
    vector<int> getMinimums(vector<int>& numbers) {
        int l = numbers.size();
        vector<int> ans(l, INT_MAX);
        numbers.emplace_back(INT_MAX);
        stack<int> s;
        for(int i = 0 ; i <= l; ++i){
            while(!s.empty() && numbers[s.top()] < numbers[i]){
                int tp = numbers[s.top()]; s.pop();
                for(int j = 0, n = !s.empty()?i-s.top()-1:i ;j<n; ++j){
                    ans[j] = min(ans[j], tp);
                }
            }
            s.push(i);
        }
        return ans;
    }
};