类型题目

1. Interval 问题
2. Two Pointers 夹逼指针
3. sweep line
4. Selection Algorithm : Kth Largest，Frequence
5. Median 系列问题：分别用一个minHeap和一个maxHeap来维护
   1. sliding window median
   2. sliding window maximum
   3. Data Stream Median

Kth Largest Element in an Array

这里用的是系统自带的最小堆，size > k时就poll()

public int findKthLargest(int[] nums, int k) {
    Queue<Integer> heap = new PriorityQueue<Integer>((a, b) -> (a - b));
    for (int i = 0; i < nums.length; i++) {
        heap.offer(nums[i]);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return heap.poll();
}

The Skyline Problem

1. 其实是一个高级的sweep line的问题
2. Interval 部分也有影子
3. 能想到这样的算法，是经过循序渐进的过程：here
4. priority queue 的remove操作复杂度为O(N)，而TreeMap为O(logN)
   • 这里的数据结构是用来弹出最高点和当前位置的height
   • 算法思维跟Interval的类似

public List<int[]> getSkyline(int[][] buildings) {
    List<int[]> heights = new ArrayList<>();
    for (int[] b: buildings) {
        heights.add(new int[]{b[0], - b[2]});
        heights.add(new int[]{b[1], b[2]});
    }
    Collections.sort(heights, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
    TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder());
    heightMap.put(0,1);
    int prevHeight = 0;
    List<int[]> skyLine = new LinkedList<>();
    for (int[] h: heights) {
        if (h[1] < 0) {
            Integer cnt = heightMap.get(-h[1]);
            cnt = ( cnt == null ) ? 1 : cnt + 1;
            heightMap.put(-h[1], cnt);
        } else {
            Integer cnt = heightMap.get(h[1]);
            if (cnt == 1) {
                heightMap.remove(h[1]);
            } else {
                heightMap.put(h[1], cnt - 1);
            }
        }
        int currHeight = heightMap.firstKey();
        if (prevHeight != currHeight) {
            skyLine.add(new int[]{h[0], currHeight});
            prevHeight = currHeight;
        }
    }
    return skyLine;
}

Trapping Rain Water II

• 同样是扫描线的问题，但是同样的增加了一个维度
• 起点是上下左右边，慢慢从边到中间包围

public int trapRainWater(int[][] heights) {
    if (heights == null || heights.length == 0 || heights[0].length == 0) return 0;

    PriorityQueue<Cell> queue = new PriorityQueue<Cell>(1, (a, b) -> (a.h - b.h));
    int n = heights.length, m = heights[0].length;
    boolean[][] visited = new boolean[n][m];

    //LEFT-RIGHT
    for (int i = 0; i < n; i++) {
        visited[i][0] = true;
        visited[i][m - 1] = true;
        queue.offer(new Cell(i, 0, heights[i][0]));
        queue.offer(new Cell(i, m - 1, heights[i][m - 1]));
    }
    //TOP-BOTTOM
    for (int i = 0; i < m; i++) {
        visited[0][i] = true;
        visited[n - 1][i] = true;
        queue.offer(new Cell(0, i, heights[0][i]));
        queue.offer(new Cell(n - 1, i, heights[n - 1][i]));
    }

    int[] xs = {0,  0, 1, -1};
    int[] ys = {1, -1, 0,  0};
    int sum = 0;
    while (!queue.isEmpty()) {
        Cell cell = queue.poll();
        for (int i = 0; i < 4; i++) {
            int nx = cell.x + xs[i];
            int ny = cell.y + ys[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                visited[nx][ny] = true;
                sum += Math.max(0, cell.h - heights[nx][ny]);
                queue.offer(new Cell(nx, ny, Math.max(heights[nx][ny], cell.h)));
            }
        }
    }//end while
    return sum;
}
class Cell {
    int x;
    int y;
    int h;
    public Cell(int x, int y, int height) {
        this.x = x;
        this.y = y;
        this.h = height;
    }
}