题意描述

在一个数组当中找到满足某种条件的区间，该区间的最大值大于等于区间的最小值的2倍，返回这种区间的个数。
首先，我们要知道在数组中找到的区间，则这个区间中的数必须是连续的，例如[1,2,3,4,5]这个数组，则它的区间可以是[1,2,3]，但不能是[1,2,4,5]。

题解

暴力解法

解题思路：

首先第一个循环，确定区间的左端点，并先进行初始化将最小值和最大值设置为左端点。第二个循环确定区间的右端点,从左端点的下一个数开始遍历，右端点每次移动时需更新出这个新的区间的最大值与最小值。如果满足条件的话，那么接下来的区间则无需判断。为什么呢？因为接下来的区间已经包含了满足条件的数。我们假设如果右端点继续右移，
情况一：新的右端点大于当前的最大值，新的区间必然满足条件。
情况二：新的右端点小于等于当前的最小值，那么最大值还是原来最大值，最小值变得更小了，仍满足条件。
情况三：新的右端点介于当前区间最大最小值之间。新的区间的最大最小值没有改变，仍然满足条件。
所以i为左端点的区间，array[j]为第一个满足条件的区间的右端点，这么以i为左端点的区间所有满足条件的区间有array.size()-j个。接着左端点进行更新，直到左端点更新到该数组的最后一个数，第一层循环结束，输出最终的答案。

图解

代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector array
     * @return long长整型
     */
    long long MaxMin(vector<int>& array) {
        // write code here
        long long ans=0;
        for(int i=0;i<array.size();i++)
        {
            int min_num=array[i];
            int max_num=array[i];
            for(int j=i+1;j<array.size();j++)
            {
                min_num=min(min_num,array[j]);
                max_num=max(max_num,array[j]);
                if(max_num>=min_num*2)
                {
                    ans+=array.size()-j;//后面的区间无需遍历，直接得到以i为左端点的所有满足条件的区间个数
                    break;
                }
            }
        }
        return ans;
    }
};

算法分析：

时间复杂度：总共两层循环，最多遍历次，所以时间复杂度为。
空间复杂度：

单调栈

解题思路：

1.利用两个单调栈，存放数组中每个元素右侧大于和小于这个元素的值。
2.利用二分法在单调栈中找到每个元素右侧第一个大于和小于这个元素两倍的数的下标
3.再次从后往前遍历原数组，以当前点(下标处的数字)为左端点，右端点为到对应的区间都是合法的，加上对应的区间数到结果数组。然后每次跟新最大的合法区间，保证当前的合法区间是最大的
首先这个方法要用到两个单调栈，存放比当前数大，并且位于当前数右边的数的坐标及大小。而则是存放比当前数小，并且位于当前数右边的数的坐标与大小。我们以ascStack栈为例，当栈中存放好数之后，我们需要更加细化的查找，即利用二分法在存放比当前数大的栈中找到第一个比当前数大两倍的数，并将其坐标赋值给maxPos数组（maxPos[i]数组表示数组中array[i]这个数右边离他最近且比它大二倍的数的位置）。desStack也是如此。当把数组中每个数中右边的离他最近的比它大两倍和比它小两倍的数的坐标都记录下来之后，我们便可以开始计算答案了。b[i]记录以array[i]为左端点的区间并且满足条件的区间个数。其计算方式与暴力法类似，其实只要区间存在有某个数大于某个数的两倍，那么这个区间再加任何数都属满足条件的。加的数无非有三种情况，比最大值大，介于最大最小值之间，比最小值小。只要原区间满足区间的最大值大于等于最小值的两倍，那么这三种情况都依然能满足条件。所以我们只要找到离最近的满足条件的就行(在和中选择较小的)。那么剩下的数不需要判断，必然满足条件。所以只有用就可以计算出以为左端点的满足条件的所有区间个数了。

图解

当然还有特殊情况需要判断一下，例如以array[i]为左端点的区间中没有找到比大两倍及比小两倍的数，那么就不存在符合条件区间吗？并不是，只有我前面一个有符合条件的区间，因为包含，所以实际的个数就是的个数。最后把所有结果累加到变量中即可。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector array
     * @return long长整型
     */
    long long MaxMin(vector<int>& array) {
        // write code here
       int n=array.size();
        vector<pair<int,int>> ascStack, desStack;    // value, pos
        vector<int> maxPos(n, n);    //右边第一个大于等于其两倍的数
        vector<int> minPos(n, n);    //右边第一个小于等于其1/2的数

        for(int i = n-1; i>=0; i--) {    // ascStack
            while(!ascStack.empty() && ascStack.back().first > array[i]) {
                ascStack.pop_back();
            }

            // binary search
            int l = 0, r = ascStack.size()-1;
            int pos = -1;
            while(l<=r) {
                int mid = l + (r-l)/2;
                if (ascStack[mid].first * 2 <= array[i]) {
                    pos = mid;
                    l = mid+1;
                } else {
                    r = mid-1;
                }
            }
            if (pos == -1) minPos[i] = n;
            else minPos[i] = ascStack[pos].second;

            ascStack.push_back({array[i], i});
        }

        for(int i = n-1; i>=0; i--) {    // desStack
            while(!desStack.empty() && desStack.back().first < array[i]) {
                desStack.pop_back();
            }

            // binary search
            int l = 0, r = desStack.size()-1;
            int pos = -1;
            while(l<=r) {
                int mid = l + (r-l)/2;
                if (desStack[mid].first >= 2 * array[i]) {
                    pos = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            if (pos == -1) maxPos[i] = n;
            else maxPos[i] = desStack[pos].second;

            desStack.push_back({array[i], i});
        }

        long long res = 0;
        vector<int> b(n);
        for(int i = n-1; i>=0; i--) {
            b[i] = n - min(minPos[i], maxPos[i]);
            if (i != n-1) b[i] = max(b[i], b[i+1]);
            res += b[i];
        }
        return res;
    }
};

算法分析

时间复杂度：二分查找的时间复杂度为，需要次二分，所以时间复杂度为。
空间复杂度：需要额外大小为n的单调栈以及各种用于中间状态记录的数组，所以空间复杂度为。