区间最小数乘区间和的最大值

思路：单调栈 + 前缀和

枚举所有以a[i]为区间最小值的情况, 贪心思想：让该区间尽可能长。

• left[i]: i左侧第一个比a[i]小的索引
• right[i]: i右侧第一个比a[i]小的索引

则区间[left[i] + 1, right[i] - 1]为a[i]为区间最小值的最优解。

class Solution {
public:
    int mintimessum(vector& a) {
        int n = a.size(), ans = 0;
        vector left(n), right(n), psum(n + 1);
        // 预处理前缀和，之后可以O(1)时间求区间和
        for (int i = 1; i <= n; ++i) psum[i] = psum[i - 1] + a[i - 1];
        stack stk, stk2;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && a[stk.top()] >= a[i]) 
                stk.pop();
            left[i] = stk.empty() ? -1 : stk.top();
            stk.push(i);
        }
        for (int i = n - 1; ~i; --i) {
            while (!stk2.empty() && a[stk2.top()] >= a[i]) 
                stk2.pop();
            right[i] = stk2.empty() ? n : stk2.top();
            stk2.push(i);
        }
        for (int i = 0; i < n; ++i) {
            ans = max(ans, a[i] * (psum[right[i]] - psum[left[i] + 1]));
        }
        return ans;
    }
};

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param a int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/f31ec24143c549fcbbfafad1d480c393?tpId=196&tqId=40511&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：woshifeiwu
    算法：
        本题要求计算：区间和 * 区间最小数，针对这两点，我们分别处理。
        1. 对于区间和，我们构造前缀和列表dp。设dp[i]表示以a[i]结尾的前缀和
            初始化：
                dp[0] = a[0]
            状态转移方程：
                dp[i] = dp[i - 1] + a[i]
            有了前缀和区间之后，对于任意闭区间[i, j]，区间和为dp[j] - dp[i]
        2. 对于区间最小数，我们维护一个单调递增的栈stack，栈内存储的是元素下标
            遍历列表a：
                如果当前元素小于栈顶元素，入栈；
                否则，出栈，计算当前 区间和 * 区间最小数，更新res
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n)
    """

    def mintimessum(self, a):
        # write code here
        n = len(a)

        dp = [0] * n
        dp[0] = a[0]
        for i in range(1, n): # 建立列表a的前缀和
            dp[i] = dp[i - 1] + a[i]

        stack, res = [], 0
        for i in range(n):
            while stack and a[i] < a[stack[-1]]:
                idx = stack.pop()
                winSum = dp[stack[-1]] if stack else 0
                res = max(res, a[idx] * (dp[i - 1] - winSum)) # 当前区间为[idx, right], right = i - 1，区间和为：dp[right] - dp[stack[-1]]，这里需要注意当stack为空
            stack.append(i)

        while stack:
            idx = stack.pop()
            winSum = dp[stack[-1]] if stack else 0
            res = max(res, a[idx] * (dp[n - 1] - winSum))

        return res


if __name__ == "__main__":
    sol = Solution()

    # a = [1, 2, 3, 4, 5]

    a = [1, 1, 1, 1, 1]

    res = sol.mintimessum(a)

    print res

import java.util.*;

/**
 * NC380 区间最小数乘区间和的最大值
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组 
     * @return int整型
     */
    public int mintimessum (ArrayList<Integer> a) {
        return solution(a);
    }

    /**
     * 前缀和 + 单调栈
     * @param a
     * @return
     */
    private int solution(ArrayList<Integer> a){
        int n = a.size();
        int[] preSum = new int[n+1];
        // 前缀和
        for(int i=1; i<=n; i++){
            preSum[i] = preSum[i-1]+a.get(i-1);
        }

        Stack<Integer> leftStack = new Stack<>();
        // leftIdx[i]: 表示以a[i]为最小值时 区间的左边界索引
        int[] leftIdx = new int[n];
        for(int i=0; i<n; i++){
            // 单调栈 单调增(从左往右) 找到左边第一个小于a[i]的索引 -1表示没找到
            while(!leftStack.isEmpty() && a.get(leftStack.peek())>=a.get(i)){
                leftStack.pop();
            }
            leftIdx[i] = leftStack.isEmpty() ? -1 : leftStack.peek();
            leftStack.push(i);
        }

        Stack<Integer> rightStack = new Stack<>();
        // rightIdx[i]: 表示以a[i]为最小值时 区间的右边界索引
        int[] rightIdx = new int[n];
        for(int i=n-1; i>=0; i--){
            // 单调栈 单调增(从右往左) 找到右边第一个小于a[i]的索引 n表示没找到
            while(!rightStack.isEmpty() && a.get(rightStack.peek())>=a.get(i)){
                rightStack.pop();
            }
            rightIdx[i] = rightStack.isEmpty() ? n : rightStack.peek();
            rightStack.push(i);
        }

        int sum = 0;
        for(int i=0; i<n; i++){
            // 区间和 * 区间最小值
            sum = Math.max(sum, (preSum[rightIdx[i]]-preSum[leftIdx[i]+1])*a.get(i));
        }

        return sum;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int mintimessum(ArrayList<Integer> aList) {
        int n = aList.size();
        int ans = 0;

        // 转换 ArrayList<Integer> 到 int[] 数组
        int[] a = aList.stream().mapToInt(Integer::intValue).toArray();

        // 以下是与之前相同的逻辑
        int[] leftmin = new int[n];
        int[] rightmin = new int[n];
        Stack<Integer> stack1 = new Stack<>();
        int[] pre = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + a[i - 1];
        }

        for (int i = 0; i < n; i++) {
            while (!stack1.isEmpty() && a[stack1.peek()] >= a[i]) {
                stack1.pop();
            }
            leftmin[i] = stack1.isEmpty() ? -1 : stack1.peek();
            stack1.push(i);
        }

        stack1.clear();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack1.isEmpty() && a[stack1.peek()] >= a[i]) {
                stack1.pop();
            }
            rightmin[i] = stack1.isEmpty() ? n : stack1.peek();
            stack1.push(i);
        }

        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, a[i] * (pre[rightmin[i]] - pre[leftmin[i] + 1]));
        }

        return ans;
    }
}

枚举1到100中的每个数字在数组中作为最小值时，乘以对应最长区间和的值，维护一个最大值。

当然，这里需要正序反序都来一遍， 防止出现有序数组这种特殊情况，对于所有数字相同的情况，最后也需要特判一下。

class Solution {
public:
    int mintimessum(vector& a) {
        // write code here
        typedef long long LL;
        int n=a.size();
        LL res=0;
        for(int i=100;i;i--){
            LL s=0;
            for(int j=0;j<n;j++){
                if(a[j]<i){
                    res=max(res,s*i);
                    s=0;
                }else{
                    s+=a[j];
                }
            }
            s=0;
            for(int j=n-1;j>=0;j--){
                if(a[j]<i){
                    res=max(res,s*i);
                    s=0;
                }else{
                    s+=a[j];
                }
            }
            if(a[0]>=i) res=max(res,s*i);
        }
        return res;
    }
};