枚举朴素解法
这道题的正解是 单调栈(柱状图最大矩形),但是我们用朴素解法 向左右扩展 也能在考试时拿到一定的分数。
题意:对数组 nums 的任意连续子数组,其「组合质量系数」为「子数组最小值 × 长度」。求所有连续子数组中该值的最大值。
朴素做法:把每个下标 i 当作子数组里的最小值,尽量向左、向右扩展,直到遇到比 nums[i] 更小的元素为止。此时以 nums[i] 为最小值的最长区间长度为 R−L+1,系数为 nums[i]×(R−L+1),对所有 i 取最大。
n 较小时 O(n2) 可通过;当 n 接近 105 时会超时,需要后面的单调栈做法。