列表

详情


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

描述

给定一个长度为 n 的正整数数组请你选出一个区间,使得该区间是所有区间中经过下述计算方法得到的值。

计算方法:区间最小值区间和

数据范围: ,区间中所有元素都满足

示例1

输入:

[1,2,3,4,5]

输出:

36

说明:

(3+4+5) \times 3 \

示例2

输入:

[1,1,1,1,1]

输出:

5

说明:

(1+1+1+1+1) \times 1 \

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C 解法, 执行用时: 16ms, 内存消耗: 2468KB, 提交时间: 2022-06-24

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param a int整型一维数组 
 * @param aLen int a数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */

// 该问题与最大直方图类似
// NC171 直方图内最大矩形
// NC237 最大矩形

int max(int a, int b) {
    return a > b ? a : b;
}

int mintimessum(int* a, int aLen ) {
    int preSum[aLen + 1];
    preSum[0] = 0;
    for (int i = 1; i < aLen + 1; i++) {
        preSum[i] = preSum[i-1] + a[i-1];
    }

    int maxResult = 0;
    int stack[100001] = { 0 }, sTop = 0;
    int i = 0, v, l, r, segmentSum;
    
    while(i < aLen) {
        while (sTop > 0 && a[i] <= a[stack[sTop - 1]]) {
            v = stack[sTop - 1];
            sTop--;
            if (sTop == 0) {
                l = 0;
            } else {
                l = stack[sTop - 1] + 1;
            }
            r = i-1;
            
            segmentSum = preSum[r+1] - preSum[l];
            
            maxResult = max(maxResult, a[v] * segmentSum);
        }
        
        stack[sTop++] = i;
        
        i++;
    }
    
    while(sTop > 0) {
        v = stack[sTop - 1];
        sTop--;
        if (sTop == 0) {
            l = 0;
        } else {
            l = stack[sTop - 1] + 1;
        }
        r = aLen - 1;
        
        segmentSum = preSum[r+1] - preSum[l];
            
        maxResult = max(maxResult, a[v] * segmentSum);
    }
        
    return maxResult;
}
//         int n = a.size();
//         int res = 0;
//         int dp[n+10];
//         dp[0] = 0;
//         stack<int> s;//单调增的栈
//         //前缀和,区间和可以由前缀相减得到
//         for(int i=1;i<=n;i++){
//             dp[i] = dp[i-1] +a[i-1];
//         }
//         for(int i=0;i<n;i++){
//             while(!s.empty() && a[i]<=a[s.top()]){
//                 int peak = a[s.top()];
//                 s.pop();
//                 int l = s.empty()? -1 : s.top();
//                 int r = i;
//                 //l和r是边界,因此区间是[l+1,r-1],其区间和dp[r+1]-dp[l]
//                 int dist = dp[r] - dp[l+1];
//                 res = max(res,peak*dist);
//             }
//             s.push(i);
//         }
//         while(!s.empty()){
//             int peak = a[s.top()];
//             s.pop();
//             int l = s.empty()? -1 : s.top();
//             int r = n; 
//             int dist = dp[r] - dp[l+1];
//             res = max(res,peak*dist);
//         }
//         return res;
//     }

C++ 解法, 执行用时: 17ms, 内存消耗: 2848KB, 提交时间: 2022-06-30

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param a int整型vector
     * @return int整型
     */
    int mintimessum(vector<int>& a) {
        // write code here
        int res = 0;
        int n = a.size();
        int dp[n + 1];
        stack<int> stk;

        dp[0] = 0;

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

        for (int i = 0; i <= n;) {
            if (i < n && (stk.empty() || a[i] > a[stk.top()])) {
                stk.push(i++);
            } else {
                if (stk.empty()) {
                    break;
                }
                int valley = a[stk.top()];
                stk.pop();
                int le = stk.empty() ? -1 : stk.top();
                int ri = i;
                int dist = dp[ri] - dp[le + 1];
                res = max(res, valley * dist);
            }
        }

        return res;
    }
};

C++ 解法, 执行用时: 17ms, 内存消耗: 2848KB, 提交时间: 2022-03-23

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @return int整型
     */
    int mintimessum(vector<int>& a) {
        // write code here
        int n = a.size();
        int res = 0;
        int dp[n+10];
        dp[0] = 0;
        stack<int> s;//单调增的栈
        //前缀和,区间和可以由前缀相减得到
        for(int i=1;i<=n;i++){
            dp[i] = dp[i-1] +a[i-1];
        }
        for(int i=0;i<n;i++){
            while(!s.empty() && a[i]<=a[s.top()]){
                int peak = a[s.top()];
                s.pop();
                int l = s.empty()? -1 : s.top();
                int r = i;
                //l和r是边界,因此区间是[l+1,r-1],其区间和dp[r+1]-dp[l]
                int dist = dp[r] - dp[l+1];
                res = max(res,peak*dist);
            }
            s.push(i);
        }
        while(!s.empty()){
            int peak = a[s.top()];
            s.pop();
            int l = s.empty()? -1 : s.top();
            int r = n; 
            int dist = dp[r] - dp[l+1];
            res = max(res,peak*dist);
        }
        return res;
    }
};

C++ 解法, 执行用时: 18ms, 内存消耗: 2836KB, 提交时间: 2022-07-17

class Solution {
  public:
    int mintimessum(vector<int>& a) {
        int z = 0;
        int h = a.size();
        int b[h + 1];
        stack<int> s;
        b[0] = 0;        
        for (int i = 1; i <= h; i++) {
            b[i] = b[i - 1] + a[i - 1];
        }
        
        for (int i = 0; i <= h;) {
            if (i < h && (s.empty() || a[i] > a[s.top()])) {
                s.push(i++);
            } else {
                if (s.empty()) {
                    break;
                }
                int x = a[s.top()];
                s.pop();
                int r = s.empty() ? -1 : s.top();
                int t = i;
                int y = b[t] - b[r + 1];
                z = max(z, x * y);
            }
        }
        return z;
    }
};

C 解法, 执行用时: 19ms, 内存消耗: 2372KB, 提交时间: 2022-07-17

int max(int a, int b) {
    return a > b ? a : b;
}

int mintimessum(int* a, int aLen ) {
    int y[aLen + 1];
    y[0] = 0;
    for (int i = 1; i < aLen + 1; i++) {
        y[i] = y[i-1] + a[i-1];
    }

    int z = 0;
    int s[100001] = { 0 }, t = 0;
    int i = 0, v, l, r, x;
    
    while(i < aLen) {
        while (t > 0 && a[i] <= a[s[t - 1]]) {
            v = s[t - 1];
            t--;
            if (t == 0) {
                l = 0;
            } else {
                l = s[t - 1] + 1;
            }
            r = i-1;           
            x = y[r+1] - y[l];            
            z = max(z, a[v] * x);
        }        
        s[t++] = i;        
        i++;
    }
    
    while(t > 0) {
        v = s[t - 1];
        t--;
        if (t == 0) {
            l = 0;
        } else {
            l = s[t - 1] + 1;
        }
        r = aLen - 1;       
        x = y[r+1] - y[l];           
        z = max(z, a[v] * x);
    }      
    return z;
}

上一题