475 Heaters

给一串暖气所在index的数组 和一串房子所在index的数组 求暖气的最小cover半径

思路是把房子穿插在排好序的暖气数组中 求每个房子距离其两侧暖气的距离取最小值(有一个暖气照应到就可以)

然后我们取这些最小值中的最大值

Java Internal Method: Binary Search

Return Value

This method returns index of the search key, if it is contained in the array, else it returns (-(insertion point) - 1). The insertion point is the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key.

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        //place the houses into the heaters array 
        Array.sort(heaters);
        int firstHeaterIdx = 0;
        int lastHeaterIdx = healters.length;
        int res = 0;
        for(Integer house: houses) {
            int housePos =  Arrays.binarySearch(heaters, house);
            int dist1 = (housePos == lastHeaterIdx) Integer.MAX_VALUE : (heaters[housePos] - house);
            int dist2 = (housePos == 0) Integer.MAX_VALUE : (house - heaters[housePos - 1]);
            res = Math.max(res,Math.min(dist1,dist2));
        }
        return res;
    }
}

363. Max Sum of Rectangle No Larger Than K

There are many possible form of a rectangle constructed. A naive way is to construct lines by line and using the sum array technique to compute the sum of areas so far. Consider the situation when there is only 1D array.

 public int maxSumSubmatrix(int[][] matrix, int target) {
    int row = matrix.length;
    if(row==0)return 0;
    int col = matrix[0].length;
    int m = Math.min(row,col);
    int n = Math.max(row,col);
    //indicating sum up in every row or every column
    boolean colIsBig = col>row;
    int res = Integer.MIN_VALUE;
    for(int i = 0;i < m;i++){
        int[] array = new int[n];
        // sum from row j to row i
        for(int j = i;j >= 0;j--){
            int val = 0;
            TreeSet<Integer> set = new TreeSet<Integer>();
            set.add(0);
            //traverse every column/row and sum up
            for(int k = 0;k<n;k++){
                array[k] = array[k]+(colIsBig?matrix[j][k]:matrix[k][j]);
                val = val + array[k];
                //use  TreeMap to binary search previous sum to get possible result 
                Integer subres = set.ceiling(val-target);
                if(null!=subres){
                    res=Math.max(res,val-subres);
                }
                set.add(val);
            }
        }
    }
    return res;
}