题解 | #牛牛构造等差数列#

单调队列解法，考虑任意端点 结尾的极大子区间，其满足区间内任意一子区间都不能满足条件。之后考虑 对不满足条件区间个数的贡献，加和即可。

时间复杂度 ，空间复杂度 。

class Solution
{
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector array
     * @return long长整型
     */
    long long MaxMin(vector<int> &array)
    {
        long long r = 0;
        long long l = 0;
        deque<long long> mx;
        deque<long long> mi;
        long long ans = 0;
        while (r < array.size())
        {
            while (!mx.empty() && array[r] >= array[mx.back()])
            {
                mx.pop_back();
            }
            mx.push_back(r);
            while (!mi.empty() && array[r] <= array[mi.back()])
            {
                mi.pop_back();
            }
            mi.push_back(r);

            while (array[mx.front()] >= 2 * array[mi.front()])
            {
                l++;
                if (mx.front() < l)
                    mx.pop_front();
                if (mi.front() < l)
                    mi.pop_front();
            }
            ans += r - l + 1;
            r++;
        }

        return (1 + array.size()) * array.size() / 2 - ans;
    }
};