最大化最小值的问题。

方法一：直接做，顺便复习一下迭代器和lower_bound的用法。

class Solution {public:    int findRadius(vector
     
      & houses, vector
      
       & heaters) {        sort(houses.begin(),houses.end());        sort(heaters.begin(),heaters.end());        int maxdis=0;        for (int i=0;i
       
        =heaters[heaters.size()-1]){                maxdis=max(houses[i]-heaters[heaters.size()-1],maxdis);            }else{                auto pos=lower_bound(heaters.begin(),heaters.end(),houses[i]);                int tmp=min(houses[i]-*(--pos), *pos-houses[i]);                maxdis = max(tmp,maxdis);            }        }        return maxdis;    }};
       
      
     

 

方法二：分别计算每个house左面和右面距离最近的heater。时间复杂度比上述要低。学习一下 *max_element 和 *min_element 的用法。

class Solution {public:    int findRadius(vector
     
      & houses, vector
      
       & heaters) {        int m=houses.size(), n=heaters.size();         sort(houses.begin(),houses.end());        sort(heaters.begin(),heaters.end());        vector
       
         res(m,INT_MAX);                for (int i=0,j=0;i
        
         
          =0&&j>=0;){            if (houses[i]>=heaters[j]){res[i] = min(houses[i]-heaters[j],res[i]); --i;}            else --j;        }        return *max_element(res.begin(),res.end());    }};