安插哨兵版单调栈 + 前缀和
核心思路
- 因为nums数组的每个值都可以作为子数组的最小值
- 所以对于nums的每个元素,贪心的使以nums[i]为最小值的子序列最长
- 为了使子序列最长,那么就要在nums[i]的左边找第一个小于它的数,在nums[i]的右边同样找第一个小于它的数(单调栈即可)
- 最后遍历一遍整个数组,求出所有子序列当中的最大值即可
安插哨兵版单调栈
步骤:
初始化单调栈时给单调栈插入一个哨兵,这个哨兵比所有要入栈的元素都大(或小)取决于当前栈是单调递减还是递增
,
这样就可以保证将所有元素都pop出去,最后栈中只剩下这个哨兵
普通的单调栈最后还剩下一个元素,所以需要特判剩下的那一个元素
typedef long long LL;
const int N = 100010;
int h[N], l[N], r[N], q[N];
LL s[N];
class Solution {
public:
int maxSumMinProduct(vector<int>& nums) {
int n = nums.size();
for (int i = 1; i <= n; i ++ ) {
h[i] = nums[i - 1];
s[i] = s[i - 1] + h[i];
}
h[0] = h[n + 1] = 0;
int tt = 0;
q[0] = 0; //给栈初始化一个小于所有要放进来的数的数,保证所有数都能pop出栈
//最后栈中只剩下0这个元素
for (int i = 1; i <= n; i ++ ) {
while (h[i] <= h[q[tt]]) tt -- ;
l[i] = q[tt];
q[ ++ tt] = i;
}
tt = 0;
q[0] = n + 1; //给栈初始化一个大于所有要放进来的数的数,保证所有数都能pop出栈
//最后栈中只剩下n + 1这个元素
for (int i = n; i; i -- ) {
while (h[i] <= h[q[tt]]) tt -- ;
r[i] = q[tt];
q[ ++ tt] = i;
}
LL res = 0;
for (int i = 1; i <= n; i ++ )
//因为求出来的l[i]和r[i]都是第一个大于nums[i]的数,所以实际上子序列的两个端点都要向里面缩一格
res = max(res, h[i] * (s[r[i] - 1] - s[l[i]]));
return res % 1000000007;
}
};
同时左栈初始化时丢入0,右栈丢入n-1,这样数组h的头(1)和尾(n)元素就不用特殊判断边界