LeetCode_单调栈_中等_907.子数组的最小值之和

Dear 丶 2023-10-06 23:53 8阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此返回答案模 109 \+ 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 \* 104  
1 <= arr\[i\] <= 3 \* 104

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/sum-of-subarray-minimums

## 2.思路 ##

（1）暴力穷举法  
暴力穷举法比较容易想到，直接 2 层 for 循环枚举所有的子数组，并且用变量 minNum 记录每个子数组的最小值，以及使用变量 res 保存每个子数组的 minNum 的累加和（每个 minNum 都经过模 109 \+ 7 处理），当变量结束后直接返回 res 即可。不过**该方法的时间复杂度较高，为 O(n2)**，并且在 LeetCode 中提交时会出现“超出时间限制”的提示。

（2）单调栈  
思路参考[该 LeetCode 用户题解][LeetCode]。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int sumSubarrayMins(int[] arr) {
        
            int MOD_NUM = 1000000007;
            int res = 0;
            int length = arr.length;
            int minNum;
            for (int i = 0; i < length; i++) {
        
                // minNum 表示当前子数组的最小值
                minNum = arr[i];
                for (int j = i; j < length; j++) {
        
                    if (arr[j] < minNum) {
        
                        //更新 minNum
                        minNum = arr[j];
                    }
                    res = (res + minNum) % MOD_NUM;
                }
            }
            return res;
        }
    }

//思路2————单调栈
    class Solution {
        
        public int sumSubarrayMins(int[] arr) {
        
            int MOD_NUM = 1000000007;
            int length = arr.length;
            //每个元素辐射范围的左边界
            int[] left = new int[length];
            //每个元素辐射范围的右边界
            int[] right = new int[length];
            Stack<Integer> stack = new Stack<>();
            //第一次遍历先找到所有元素的左边界
            for (int i = 0; i < length; i++) {
        
                //向左找第一个小于等于 nums[i] 的元素
                while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
        
                    stack.pop();
                }
                left[i] = stack.isEmpty() ? -1 : stack.peek();
                //下标入栈
                stack.push(i);
            }
            stack.clear();
            //第二次遍历找到所有元素的右边界
            for (int i = length - 1; i >= 0; i--) {
        
                //向右找第一个小于等于 nums[i] 的元素
                while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
        
                    stack.pop();
                }
                right[i] = stack.isEmpty() ? length : stack.peek();
                //下标入栈
                stack.push(i);
            }
            long res = 0;
            for (int i = 0; i < length; i++) {
        
                res = (res + (long) (i - left[i]) * (right[i] - i) * arr[i]) % MOD_NUM;
            }
            return (int) res;
        }
    }
    
    //另一种只需遍历一次的写法
    class Solution {
        
        public int sumSubarrayMins(int[] arr) {
        
            int MOD_NUM = 1000000007;
            int length = arr.length;
            long res = 0;
            Stack<Integer> stack = new Stack<>();
            /*
                将下标 -1 和 length 作为两个哨兵元素，它们对应的元素为 MIN_VALUE
                -1 作为最左边界，length 作为最右边界
            */
            for (int i = -1; i <= length; i++) {
        
                // 向左寻找第一个小于等于A[i]的元素
                while (!stack.isEmpty() && getElement(arr, length, stack.peek()) > getElement(arr, length, i)) {
        
                    /*
                        A[cur] 就是之前思路中的 A[i]，注意区分和上面代码的区别
                        对于每个出栈元素来说，i 就是它们的右边界，而栈顶元素就是左边界
                    */
                    int cur = stack.pop();
                    // 计算贡献值
                    res = (res + (long) (cur - stack.peek()) * (i - cur) * arr[cur]) % MOD_NUM;
                }
                stack.push(i);
            }
            return (int) res;
        }
        
        // 重写根据下标取值方法，-1和n返回MIN_VALUE
        private int getElement(int[] arr, int n, int i) {
        
            if (i == -1 || i == n) {
        
                return Integer.MIN_VALUE;
            }
            return arr[i];
        }
    }

[LeetCode]: https://leetcode.cn/problems/sum-of-subarray-minimums/solution/xiao-bai-lang-dong-hua-xiang-jie-bao-zhe-489q/