高频 凳子上坐人

在一排座位中，找到与两边人距离的最远的位置

class Solution {
    public int findSeat(int[] people) {
        if (people == null || people.length == 0) {
            return -1;
        }

        int idx = -1;
        int maxLen = Integer.MIN_VALUE;
        int cnt = 0;
        for (int i = 0; i < people.length; i++) {
            if (people[i] == 0) {
                cnt++;
            } else {
                if (cnt > maxLen) {
                    maxLen = cnt;
                    idx = i - cnt;
                }
                cnt = 0;
            }
        }

        if (idx == -1) {
            return -1;
        }
        return idx + maxLen / 2;
    }
}

Follow-up:
凳子上一开始没有人，然后一个一个往里面放，每次放的时候O(1)时间求放在哪里距离最大（数学问题 )

search O(1)

Use priority queue (maxHeap)

class Solution {
    public int[] findSeat(int numOfPeople, int seats) {
        if (seats == 0) {
            return -1;
        }

        Comparator<int[]> comp = new ComparatorMax();
        PriorityQueue<int[]> q = new PriorityQueue<>(2 * seats, comp);
        int[] rst = new int[seats];

        q.offer(new int[] {0, seats});

        for (int i = 0; i < numOfPeople; i++) {
            int[] l = q.poll();
            int idx = l[0] + l[1] / 2;
            rst[idx] = i;
            q.offer(new int[] {l[0], l[1] / 2});
            q.offer(new int[] {idx + 1, l[1] - l[1]/ 2 - 1});
        }
    }

    return rst;
}

class ComparatorMax implements Comparator<Integer> {
    @Override
    public int compare(int[] a, int[] b) {
        if (a[1] > b[1]) {
            return -1;
        }

        if (a[1] < b[1]) {
            return 1;
        }

        if (a[0] < b[0]) {
            return -1;
        } else if (a[0] > b[0]) {
            return 1;
        }

        return 0;
    }
}