Greedy

经典题目

11 Container With Most Water

Maintain a global res. Start from the two ends and move towards the middle using two pointers. Every time we try to increase the height: we pick the lower side, and move that index to the next element, so as to ensure we have the maximum area of current width.

public int maxArea(int[] height) {
    if (height == null || height.length == 0) return 0;
    int res = 0;
    int i = 0, j = height.length - 1;
    while(i < j) {
        int cur = (j - i) * Math.min(height[i], height[j]);
        res = Math.max(res, cur);
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

134 Gas Station

Based on two facts:

1. if start from A we cannot reach B, then any gas station in the between cannot reach B. (B is the first one cannot reach)

2. if total gas >= total cost, there must be a solution

public int canCompleteCircuit(int[] gas, int[] cost) {
    int start = 0;
    int tank = 0;
    int total = 0;
    for (int i = 0; i < gas.length; i++) {
        if (tank + gas[i] - cost[i] < 0) {
            start = i + 1;
            tank = 0;
        } else {
            tank += gas[i] - cost[i];
        }
        total += gas[i] - cost[i];
    }
    return total >= 0 ? start : -1;
}

621. Task Scheduler

It's easier to get the number of empty slots first.

/*
    A * * * *
    A * * * *
    A * * * *
    A
    
    total number of empty slots = (map['A'] - 1) * n
*/
public int leastInterval(char[] tasks, int n) {
    int[] map = new int[26];
    for (char c : tasks) {
        map[c - 'A']++;
    }
    Arrays.sort(map);
    int max = map[25] - 1;
    int emptySlots = n * max;
    for (int i = 24; i >= 0 && map[i] > 0; i--) {
        emptySlots -= Math.min(map[i], max);
    }
    return emptySlots > 0 ? emptySlots + tasks.length : tasks.length;
}

885 Boats to Save People

/*
	Method 1: Greedy.
	Always pick one big number and one small number, and determine whether the sum is larger than limit or not.
		
	First of all, sort the array in increasing order.
	Then, use two pointers to search from two sides of the array, and check the relation between the sum and limit.
	If sum <= limit, meaning these two persons could share a same boat. So, we move on to the next couple.
	If sum > limit, we try to send larger person first, because that way, we are more likely to let two persons in the remaining share the same boat.
*/
	
public int numRescueBoats(int[] people, int limit) {        
    Arrays.sort(people);
    int left = 0, right = people.length - 1;
    int ans = 0;
    while (left < right) {
        if (people[right] + people[left] > limit) {
            ans += 1;
            right--;
        } else {
            ans += 1;
            right--;
            left++;
        }
    }
    return left == right ? ans + 1 : ans;
}