最大最小

[编程题]最大最小

热度指数：205 时间限制：C/C++ 4秒，其他语言8秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹有一个数组array，她想知道里面有多少个区间满足区间最大值大于等于区间最小值的两倍。返回满足条件的区间个数。

示例1

输入

[1,2]

输出

说明

只有区间[1,2]满足

备注:

给定Array数组

算法知识视频讲解

一只老风铃

只要找到第一个满足最大值大于等于2倍最小值的子区间，那么包含这个子区间的区间一定都满足要求。

    long long MaxMin(vector<int>& array) {
        // write code here
        
        long long count=0;
        int len=array.size();
        for(int i=0;i<len;i++)
        {
            int m_max=array[i];
            int m_min=array[i];
            if(m_max==0 && m_min==0)
                count++;
            for(int j=i+1;j<len;j++)
            {
                if(array[j]>m_max)
                    m_max=array[j];
                if(array[j]<m_min)
                    m_min=array[j];
                if(m_max>=2*m_min)  //只要找到第一组满足要求的区间=》那么后面的区间一定也满足
                {
                    count+=len-j;
                    break;   //后面的区间不再需要计算
                }  
            }
        }
        return count; 
    }

发表于 2021-03-18 09:46:23 回复(0)

科大15届软工代言人

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 array
     * @return long长整型
     */
    public long MaxMin (int[] array) {
        if(array == null || array.length == 0) {
            return 0;
        }
        LinkedList<Integer> minQueue = new LinkedList<>();
        LinkedList<Integer> maxQueue = new LinkedList<>();
        int left = 0;
        long count = 0;
        int right = 0;
        
        while(left < array.length) {
            while(right < array.length) {
                while(!minQueue.isEmpty() && array[minQueue.peekLast()] > array[right]) {
                    minQueue.pollLast();
                }
                minQueue.offerLast(right);
                while(!maxQueue.isEmpty() && array[maxQueue.peekLast()] < array[right]) {
                    maxQueue.pollLast();
                }
                maxQueue.offerLast(right);
                if(array[maxQueue.peekFirst()] >= array[minQueue.peekFirst()] * 2) {
                    count += array.length - Math.max(maxQueue.peekFirst(),minQueue.peekFirst());
                    break;
                }
                right++;
            }
            //新的开始
            left++;
            right = left;
            maxQueue.clear();
            minQueue.clear();
        }
        return count;
    }
}

发表于 2021-07-07 00:41:42 回复(0)

lazywg

用最笨的办法，解析数组所有连续区间，并判断最大值是否最小值两倍。

	未通过性能测试



	
package com.lazywg.study;

/**
 * @author gaowang
 * @createTim 2020/8/30 13:24
 */
public class Solution {
    /**
     *
     * @param array int整型一维数组 array
     * @return long长整型
     */
    public long MaxMin (int[] array) {
        // write code here
        int count = 0, min = 0, max = 0;
        for (int i = 2; i <= array.length; i++) {
            for (int j = 0; j < (array.length - i + 1); j++) {
                min = array[j];
                max = array[j];
                for (int k = j + 1; k < j + i; k++) {
                    if (min > array[k]) {
                        min = array[k];
                    } else if (max < array[k]) {
                        max = array[k];
                    }
                }
                if (max == 2 * min) {
                    count++;
                }
            }
        }
        return count;
    }
}

发表于 2020-08-30 14:42:38 回复(0)