单调栈练习(五)— 子数组的最小值之和

发布时间:2024年01月13日

题目
同样的LeetCode原题:题目链接

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

由于答案可能很大,因此 返回答案模 10^9 + 7 。

在这里插入图片描述

思路

暴力解
先来说暴力解的思路:
三层for循环,找到每一个子数组中的最小值,0-0,0-1,0-2 … 0-N。1-1,1-2,1-3…1-N。并将每一个子数组的最小值相加即可,时间复杂度 O ( N 3 ) O(N^3) O(N3)

在这里插入图片描述

代码

public static int subArrayMinSum2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int N = arr.length;
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                int min = arr[i];
                for (int k = i + 1; k <= j; k++) {
                    min = Math.min(min, arr[k]);
                }
                ans += min;
            }
        }
        return ans;
    }

优化的普通解

优化的方法是根据题目中给定的 arr[],生成对应的 left[] 和 right[]。

left[]:left[i] = x ,表示左侧最近 <= arr[i] 的位置在 x(x表示对应的索引)
right[]:right[i] = y,表示右侧最近 < arr[i] 的位置在y(y表示对应的索引)

生成 left[] 和 right[]的作用在于,根据当前子数组中最小值 arr[i] 在 left[]、right[]中获取左右最小且近的边界值后,直接进行计算求出以 arr[i] 作为子数组最小值的累加和,优化后的时间复杂度是 O ( N ) O(N) O(N)

来看下面的例子:当前 arr[8] = 7 ,找到左侧最近且小的值在是4位置的3,右侧最近且小的值是12位置4。
在这里插入图片描述

此时,以7作为最小值的子数组范围是 5 ~ 11,并且此范围内所有值都是 >= 7 的,但是因为要以7作为最小值,所以5 ~ 11范围内所求的子数组要把8位置的7涵盖进去。此时利用 left[8] = 4 、right[8] = 12, (8 - 4)x(12 - 8)x (arr[8]) = 112,就是7作为最小值的时候所有子数组最小值的累加和。

需要注意的是:如果是普通的无重复值数组,那么很好处理,但如果数组中有重复值,就需要额外注意!!!

举例:
在这里插入图片描述
碰上有重复值的数组,要稍微多考虑一些,就是左右边界的设定选择改怎么选?本题中答案选用的是第一种

两种选择的不同其实目的都是一个,那就是抛去重复值的计算

比如说:
此时以4位置的3作为最小值,如果依然是从1位置开始枚举每个子数组 1 - 4 、 1 - 5 … 1 - 11,那等到以7位置的3作为最小值时呢? 此时如果再从1 - 7、 1 - 8 … 1 - 11。那么和之前计算的子数组最小值就包含了重复的部分。所以要去重。

代码

构建完成后,遍历一遍 arr[] , 将每一个值都作为子数组的最小值,并根据 left[]、right[] 算出子数组的个数,个数 * 最小值,不就是我们想要的答案,再将求出来的每一个结果进行累加。

 public static int subArrayMinSum2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
   
        int[] left = leftNearLessEqual1(arr);
        int[] right = rightNearLess1(arr);
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            int start = i - left[i];
            int end = right[i] - i;
            ans += start * end  * arr[i];
        }
        return ans;
    }

    public static int[] rightNearLess1(int[] arr) {

        int N = arr.length;
        int[] right = new int[N];
        int ans;

        for (int i = 0; i < N; i++) {
            ans = N;
            for (int j = i + 1; j < N; j++) {
                if (arr[j] < arr[i]) {
                    ans = j;
                    break;
                }
            }
            right[i] = ans;
        }
        return right;
    }

    public static int[] leftNearLessEqual1(int[] arr) {
        int N = arr.length;
        int[] left = new int[N];
        int ans;
        for (int i = N - 1; i >= 0; i--) {
            ans = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] <= arr[i]) {
                    ans = j;
                    break;
                }
            }
            left[i] = ans;
        }
        return left;
    }

单调栈
单调栈其实就是将构建left[]、right[]的过程加快了,其逻辑是不变的。
这里的单调栈是自己用数组实现,没有用系统提供的Stack,但是照比系统提供的性能要更好一些。

 public static int sumSubarrayMins(int[] arr) {

       if (arr == null || arr.length == 0) {
           return 0;
       }

       int[] stack = new int[arr.length];
       int[] left = leftNearLessEqual2(arr, stack);
       int[] right = rightNearLess2(arr, stack);
       long ans = 0;

       for (int i = 0; i < arr.length; i++) {
           long start = i - left[i];
           long end = right[i] - i;
           ans += (start * end) * arr[i];
           ans %= 1000000007;
       }
       return (int)ans;
   }

    public static int[] rightNearLess2(int[] arr,int[] stack) {

        int N = arr.length;
        int[] right = new int[N];
        int size = 0;

        for (int i = 0; i < N; i++) {
          while (size != 0 && arr[i] < arr[stack[size - 1]]){
              right[stack[--size]] = i;
          }
          stack[size++] = i;
        }

        while (size != 0){
            right[stack[--size]] = N;
        }

        return right;
    }

    public static int[] leftNearLessEqual2(int[] arr,int[] stack) {
        int N = arr.length;
        int[] left = new int[N];
        int size = 0;
        for (int i = N - 1; i >= 0; i--) {
            //stack[size - 1] :当前最后加入到数组中元素即为栈顶元素
            //stack[--size] :出栈操作,弹出栈顶元素并且大小 - 1,后加入的元素要覆盖当前位置
            while (size != 0 && arr[i] <= arr[stack[size - 1]]){
                //当前 i 位置 使栈顶元素出栈,所以 left[栈顶元素左侧小且近] = 当前下标 i
                left[stack[--size]] = i;
            }
            //入栈操作:存储当前元素索引
            stack[size++] = i;
        }
        while (size != 0){
            left[stack[--size]] = -1;
        }
        return left;
    }
文章来源:https://blog.csdn.net/weixin_43936962/article/details/135555457
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。