NC380. 区间最小数乘区间和的最大值
描述
示例1
输入:
[1,2,3,4,5]
输出:
36
说明:
示例2
输入:
[1,1,1,1,1]
输出:
5
说明:
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; }