题解 | #最大最小#

题意整理

给定一个数组。
求所有的区间中，满足区间最大值大于等于最小值对应的区间个数。

方法一（暴力）

1.解题思路

先确定左端点，然后遍历所有的右端点。
每次记录最大值和最小值，只要最大值大于等于最小值，则结束内循环。将满足条件的区间数加入到结果变量。
直到确定完所有的左端点。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 array
     * @return long长整型
     */
    public long MaxMin (int[] array) {
        int n=array.length;
        //初始化区间计数变量
        long cnt=0L;
        for(int i=0;i<n;i++){
            //记录最小值和最大值
            int min=array[i];
            int max=array[i];
            for(int j=i+1;j<n;j++){
                min=Math.min(min,array[j]);
                max=Math.max(max,array[j]);
                //如果当前最大值大于等于最小值两倍
                if(max>=min*2){
                    //左端点为i，右端点为j到n-1对应的区间都是合法的
                    cnt+=n-j;
                    break;
                }
            }
        }
        return cnt;
    }
}

3.复杂度分析

时间复杂度：总共两层循环，最多遍历 $n(n-1)/2$ 次，所以时间复杂度为 $O(n^2)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。

方法二（单调栈+二分）

1.解题思路

首先初始化两个单调栈，一个记录递增序列，一个记录递减序列。
从后往前遍历原数组，所以单调栈记录的值一定在当前数字对应下标之后的位置。然后找到右边第一个小于等于其二分之一的数对应的下标、右边第一个大于等于其两倍的数对应的下标，记录到对应的数组。
再次从后往前遍历原数组，以当前点(下标i处的数字)为左端点，右端点为 $min(minPos[i],maxPos[i])$ 到 $n-1$ 对应的区间都是合法的，加上对应的区间数到结果数组。然后每次跟新最大的合法区间，保证当前的合法区间是最大的。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 array
     * @return long长整型
     */
    public long MaxMin (int[] array) {
        int n=array.length;
        long cnt=0;
        //维护一个递增序列
        ArrayList<int[]> asc=new ArrayList<>();
        //维护一个递减序列
        ArrayList<int[]> desc=new ArrayList<>();
        //记录右边第一个大于等于当前数字两倍的数对应的下标
        int[] maxPos=new int[n];
        //记录右边第一个小于等于当前数字二分之一的数对应的下标
        int[] minPos=new int[n];
        for(int i=n-1;i>=0;i--){
            while(!asc.isEmpty()&&asc.get(asc.size()-1)[0]>array[i]){
                asc.remove(asc.size()-1);
            }
            //二分查找对应下标
            int pos=binarySearch1(asc,array[i]);
            if(pos==-1){
                minPos[i]=n;
            }
            else{
                minPos[i]=asc.get(pos)[1];
            }
            //添加当前元素及其下标
            asc.add(new int[]{array[i],i});
        }

        for(int i=n-1;i>=0;i--){
            while(!desc.isEmpty()&&desc.get(desc.size()-1)[0]<array[i]){
                desc.remove(desc.size()-1);
            }
            //二分查找对应下标
            int pos=binarySearch2(desc,array[i]);
            if(pos==-1){
                maxPos[i]=n;
            }
            else{
                maxPos[i]=desc.get(pos)[1];
            }
            //添加当前元素及其下标
            desc.add(new int[]{array[i],i});
        }

        //记录当前下标为左端点时，对应的合法区间数
        int[] b=new int[n];
        for(int i=n-1;i>=0;i--){
            //左端点为i，右端点为min(minPos[i],maxPos[i])到n-1对应的区间都是合法的
            b[i]=n-Math.min(minPos[i],maxPos[i]);
            //每次取最大的区间数作为合法区间数
            if(i!=n-1){
                b[i]=Math.max(b[i],b[i+1]);
            }
            cnt+=b[i];
        }
        return cnt;
    }

    //找到target右边第一个小于等于其二分之一的数对应的下标
    private int binarySearch1(ArrayList<int[]> asc,int target){
        int l=-1,r=asc.size()-1;
        while(l<r){
            //上取整，防止死循环
            int mid=l+(r-l+1)/2;
            if(asc.get(mid)[0]*2<=target){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        return l;
    }

    //找到target右边第一个大于等于其两倍的数对应的下标
    private int binarySearch2(ArrayList<int[]> desc,int target){
        int l=-1,r=desc.size()-1;
        while(l<r){
            //上取整，防止死循环
            int mid=l+(r-l+1)/2;
            if(desc.get(mid)[0]>=2*target){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        return l;
    }
}

3.复杂度分析

时间复杂度：二分查找的时间复杂度为 $O(log_2n)$ ，二分外面还嵌套一层循环，所以时间复杂度为 $O(nlog_2n)$ 。
空间复杂度：需要额外大小为n的单调栈以及各种用于中间状态记录的数组，所以空间复杂度为 $O(n)$ 。