1. 题面
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
示例 1：
输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
示例 2：
输入：arr = [11,81,94,43,3]
输出：444
提示：
1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 3 * 104
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-subarray-minimums
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题分析
首先对题意进行理解,题目给的示例1的含义是:
通过穷举出题目所给出的
nums所延伸出的所有子数组,然后找出这些子数组中的最小值,然后把他们加起来,这样就能够求出来答案。
那么这样的暴力解法的时间复杂度是多少呢?
首先对于暴力回溯求所有子数组,就相当于求子集的问题,最坏情况下会去到2^n的时间复杂度,然后每个子数组都遍历一次求min,最坏情况下会去到n的时间复杂度,最终就是
O(2^n*n)的时间复杂度,一看题目给的length,必然超时。
回过头来考虑这个问题的话,可以这样想,对于每一个nums[i]所在的区间,nums[i]都有可能作为一个最小值而存在,那么什么时候是最小值呢?如果我们能够找到一个区间j∈[left,right],其中,所有的nums[i]<=nums[j],这时候nums[i]就可以作为一个最小值。
注:这里这样做是会导致重复元组的出现的,因此需要限定一下左右边界的大小。
对于左边界,我们允许
nums[i]<=nums[j], 但是对于右边界,我们只 允许nums[i]<nums[j]
那么一个简单的思路就是从nums[i]开始,从两边出发,找到一个符合条件的[left,right],最终结算即可。
结算的公式:
//先来考虑只有如果只有一边的边界,这时候会如何
//假定nums[left]是在nums[i]左边,第一个比nums[i]要小的数的下标
int score1 = (i-left)*nums[i];
//假定nums[right]是在nums[i]右边,第一个比nums[i]要小的数的下标
int socre2 = (right-i)*nums[i];
//对于边界而言
//如果左边没有更小的数了,那么
int left = -1;
//对于右边界而言
//如果右边没有更小的数了,那么
int right = n;
//由于最终的子数组是两边延伸后得到的结果
int total = (i-left)*(right-i)*nums[i];3.单调栈分析
我们知道,如果是两边延伸的办法的话,那么最终的时间复杂度会去到O(n^2),最终测试用例的处理次数会去到8次方,大概率是会超时的,如果能够找到一个每个元素只遍历一次,而又能准确地知道其左右边界的算法,那么这道题就迎刃而解了。
单调栈符合这样的要求。
我们要求每一个
nums[i]在栈中,第一个压着的肯定是它左边第一个比它小的数,因此if(nums[stack.peek()] <= nums[i]){//如果栈顶元素比当前检索到的元素要小,那么就入栈 stack.push(i); }同时,我们希望能够找到它右边第一个比它小的数,因此
if(nums[stack.peek()] > nums[i]){//如果栈顶元素比当前检索到的元素要大,那么就出栈并结算 int peek = stack.pop(); socore = (i-stack.peek())*(peek-i)*nums[peek]; }
这个就是单调栈的大致思路,最终累加socre即可
4. AC代码
首先回顾一下单调栈的模板
vector<vector<int>> getNear(vector<int>& nums){
vector<vector<int>> ans(nums.size());
stack<vector<int>> s;
for(int i =0;i<nums.size();i++){
while (!s.empty() && nums[s.top()[0]]>nums[i]){//如果栈顶元素比当前的检索元素要大,那么就结束它
//检查左边元素和右边元素,设置答案
vector<int> top = s.top();
s.pop();
for(int j = 0;j<top.size();j++){//结算该列表中的元素
int idx = top[j];
//然后ans[i][0]就是左边离他最近的那个元素,是栈的下边
//ans[i][1]就是右边离他最近的那个元素
int left = s.empty()?-1:s.top().back();
ans[idx].push_back(left);
ans[idx].push_back(i);
}
}
if(!s.empty() && nums[s.top()[0]] == nums[i]){
s.top().push_back(i);
}else{
vector<int> v;
v.push_back(i);
s.push(v);
}
}
while (!s.empty()){
vector<int> v= s.top();
s.pop();
int left = s.empty()?-1:s.top().back();
for(int i = 0;i<v.size();i++){
ans[v[i]].push_back(left);
ans[v[i]].push_back(nums.size());
}
}
return ans;
}class Solution {
//求解一个列表,这个列表定义
//对于nums[i],找到一个nums[left]是第一个比它小的,找到一个nums[right]是第一个比它小的
//定义arr[i][2]={left,right}
static final int mod = (int)(1e9+7);
public int sumSubarrayMins(int[] nums) {
int n = nums.length;
int[][] arr = new int[nums.length][2];
Stack<List<Integer>> stack = new Stack<>();
long result = 0;
//单调栈处理
for(int i = 0;i < n;i++){
//其关键是对于左边相等的数要如何进行处理
while(!stack.isEmpty() && nums[stack.peek().get(0)] > nums[i]){
//那么就结算当前的peek()
List<Integer> peek = stack.pop();
int size = peek.size();
for(int j = 0;j< size; j++){
int left = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
int idx = peek.get(j);
if(j == 0){
arr[idx][0] = left;//左边这个元素
}else{
arr[idx][0] = peek.get(j-1);//与前面那个元素相等
}
arr[idx][1] = i;
result = (result + 1L*(arr[idx][1] - idx)*(idx - arr[idx][0])*nums[idx])%mod;
}
}
if(!stack.isEmpty() && nums[stack.peek().get(0)] == nums[i]){
stack.peek().add(i);
}else{
ArrayList<Integer> v = new ArrayList<>();
v.add(i);
stack.push(v);
}
}
//如果到最后栈都还没空,那么这时候就要手动清空
while (!stack.isEmpty()){
List<Integer> peek = stack.pop();
int size = peek.size();
int left = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
for(int i = 0;i<size;i++){
int idx = peek.get(i);
if(i == 0){
arr[idx][0] = left;
}else{
arr[idx][0] = peek.get(i-1);
}
arr[idx][1] = nums.length;
result = (result + 1L*(arr[idx][1] - idx)*(idx - arr[idx][0])*nums[idx])%mod;
}
}
/*
for(int i = 0;i< nums.length;i++){
System.out.print(i+":"+nums[i]+" ");
}
System.out.println();
for(int i = 0;i<n;i++){
System.out.println("i:"+i+",nums[i]="+nums[i]+",left:"+arr[i][0]+",right:"+arr[i][1]);
}
//然后结算即可
System.out.println(result);
*/
return (int)result;
}
}
