leetcode 907. Sum of Subarray Minimums | 907. 子数组的最小值之和（单调栈）

男娘i 2022-08-28 06:54 3阅读 0赞

## 题目 ##

[https://leetcode.com/problems/sum-of-subarray-minimums/][https_leetcode.com_problems_sum-of-subarray-minimums]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

单调栈问题。参考左神算法课：[https://ke.qq.com/webcourse/3067253/103187834\#taid=10646309101817205&vid=5285890813430715450][https_ke.qq.com_webcourse_3067253_103187834_taid_10646309101817205_vid_5285890813430715450]

相当于找当前元素属于哪些子序列的最小值，如下图，以 10 位置的 7 为例，它可以是以下标 `6~10` 任意一个作为开始，到下标 `10~14` 任意一个作为结束的所有 `5*5=25` 个子数组的最小值，所以，以 7 为最小值的 `subarray sum = 5*5*7`。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
需要注意的是出现相等数字时候的情况，具体表现为当遇到相等数字时，不重复计算即可。可以听左神讲的，也可以自己画一下，试一下就懂了。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

class Solution { 
        public static final int MOD = (int) (Math.pow(10, 9) + 7);
    
        public int sumSubarrayMins(int[] arr) { 
            int L = arr.length;
            // 找左边第一个【小于等于】h[i]的数
            // 从右向左遍历，维护单调增栈，小/等数h[i]不断将大数h[j]弹出，则h[i]左边第一个小于h[i]的数为h[j]
            Stack<Integer> valueStack = new Stack<>();
            Stack<Integer> indexStack = new Stack<>();
            int[] leftIndex = new int[L]; // i左边第一个小于i的数的下标
            Arrays.fill(leftIndex, -1);
            for (int i = L - 1; i >= 0; i--) { 
                while (!valueStack.isEmpty() && valueStack.peek() >= arr[i]) { 
                    leftIndex[indexStack.pop()] = i;
                    valueStack.pop();
                }
                valueStack.push(arr[i]);
                indexStack.push(i);
            }
            // 找右边第一个【小于】h[i]的数
            // 从左向右遍历，维护单调不减栈
            valueStack = new Stack<>();
            indexStack = new Stack<>();
            int[] rightIndex = new int[L]; // i右边第一个小于i的数的下标
            Arrays.fill(rightIndex, L);
            for (int i = 0; i < L; i++) { 
                while (!valueStack.isEmpty() && valueStack.peek() > arr[i]) { 
                    rightIndex[indexStack.pop()] = i;
                    valueStack.pop();
                }
                valueStack.push(arr[i]);
                indexStack.push(i);
            }
    
            long result = 0;
            for (int i = 0; i < L; i++) { 
                int fromRange = i - leftIndex[i];
                int toRange = rightIndex[i] - i;
                result += (long)fromRange * toRange * arr[i];
                result %= MOD;
            }
            return (int) result;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]

[https_leetcode.com_problems_sum-of-subarray-minimums]: https://leetcode.com/problems/sum-of-subarray-minimums/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/5dd8410c0795438198aa7574328b9b91.png
[https_ke.qq.com_webcourse_3067253_103187834_taid_10646309101817205_vid_5285890813430715450]: https://ke.qq.com/webcourse/3067253/103187834#taid=10646309101817205&vid=5285890813430715450
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/fa7708da832d480bab91053da7ea6590.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/00cf1fbc6d034f2e82db2801aa97dfc1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/b369193ed4814b2cb27546973c22bdd0.png