数据结构强化1

Union Find    集合合并，查找元素在集合里面

数组实现

    int[] pre;
    public int find(int x) {
        int r = x;
        while (r != pre[r]) {
            r = pre[r];
        }
        int i = x, j;
        while (pre[i] != r) {
            j = pre[i];
            pre[i] = r;
            i = j;
        }
        return r;
    }
    public void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            pre[fx] = fy;
        }
    }

hashMap实现

class UnionFind <T>{
    private Map<T, T> map = new HashMap<>();
    
    public UnionFind(Set<T> set) {
        for (T t : set) {
            map.put(t, t);
        }
    }
    
    public T find(T x) {
        T r = x;
        if (r != map.get(r)) {
            r = map.get(r);
        }
        
        T i = x, j;
        while (i != r) {
            j = map.get(i);
            map.put(i, r);
            i = j;
        }
        return r;
    }
    
    public void union(T x, T y) {
        T fx = find(x);
        T fy = find(y);
        if (fx != fy) {
            map.put(fx, fy);
        }
    }
}

 1，找无向图的联通块。 bfs

找出无向图中所有的连通块。

图中的每个节点包含一个label属性和一个邻接点的列表。（一个无向图的连通块是一个子图，其中任意两个顶点通过路径相连，且不与整个图中的其它顶点相连。）

您在真实的面试中是否遇到过这个题？ Yes
样例
给定图:

A------B  C
      |  | 
      |  |
      |  |
      |  |
      D   E
返回 {A,B,D}, {C,E}。其中有 2 个连通块，即{A,B,D}, {C,E}

标签 
相关题目 

     class UndirectedGraphNode {
         int label;
         ArrayList<UndirectedGraphNode> neighbors;
         UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
     }
     public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        
         List<List<Integer>> result = new ArrayList<>();
         if (nodes == null || nodes.size() == 0) {
             return result;
         }
         
         Map<UndirectedGraphNode, Boolean> map = new HashMap<>();
         for (UndirectedGraphNode node : nodes) {
             map.put(node, false);
         }
         
         for (UndirectedGraphNode node : nodes) {
             if (!map.get(node)) {
                 find(node, result, map);
             }
         }
         return result;
     }
    private void find(UndirectedGraphNode node, List<List<Integer>> result, Map<UndirectedGraphNode, Boolean> map) {
        ArrayList<Integer> list = new ArrayList<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        queue.offer(node);
        map.put(node, true);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                UndirectedGraphNode cur = queue.poll();
                list.add(cur.label);
                for (UndirectedGraphNode neighbor : cur.neighbors) {
                    if (!map.get(neighbor)) {
                        map.put(neighbor, true);
                        queue.offer(neighbor);
                    }
                }
            }
        }
        result.add(list);
    }

2 Find the Weak Connected Component in the Directed Graph

 class DirectedGraphNode {
              int label;
              ArrayList<DirectedGraphNode> neighbors;
              DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
          }
     public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
         List<List<Integer>> result = new ArrayList<>();
         if (nodes == null || nodes.size() == 0) {
             return result;
         }
         Set<Integer> set = new HashSet<>();
         for (DirectedGraphNode node : nodes) {
             set.add(node.label);
         }
         UnionFind uf = new UnionFind(set);
         for (DirectedGraphNode node : nodes) {
             for (DirectedGraphNode neighbor : node.neighbors) {
                 uf.union(node.label, neighbor.label);
             }
         }
         Map<Integer, List<Integer>> map = new HashMap<>();
         for (DirectedGraphNode node : nodes) {
             int parent = uf.find(node.label);
             if (!map.containsKey(parent)) {
                 map.put(parent, new ArrayList<Integer>());
             } else {
                 map.get(parent).add(node.label);
             }
         }
         for (List<Integer> list : map.values()) {
             result.add(list);
         }
         return result;
     }

3 Number of Islands

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    int m;
    int n;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {-1, 1, 0, 0};
    public int numIslands(boolean[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int islands = 0;
        m = grid.length;
        n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    islands++;
                    bfs(grid, i, j);
                }
            }
        }
        return islands;
    }
    void bfs(boolean[][] grid, int i, int j) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i * n + j);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int cur = queue.poll();
                int x = cur / n;
                int y = cur % n;
                grid[x][y] = false;
                for (int h = 0; h < 4; h++) {
                    int nx = x + dx[h];
                    int ny = y + dy[h];
                    if (isValue(grid, nx, ny)) {
                        queue.offer(nx * n + ny);
                    }
                }
            }
        }
    }
    boolean isValue(boolean[][] grid, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y];
    }
}

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    int m;
    int n;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {-1, 1, 0, 0};
    public int numIslands(boolean[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int islands = 0;
        m = grid.length;
        n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    islands++;
                    dfs(grid, i, j);
                }
            }
        }
        return islands;
    }
    void dfs(boolean[][] grid, int i, int j) {
        if (!isValue(grid, i, j)) return;
        grid[i][j] = false;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            dfs(grid, x, y);
        }
    }
    boolean isValue(boolean[][] grid, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y];
    }
}

4 3 Number of Islands 2

描述
 笔记
 数据
 评测
给定 n，m，分别代表一个2D矩阵的行数和列数，同时，给定一个大小为 k 的二元数组A。起初，2D矩阵的行数和列数均为 0，即该矩阵中只有海洋。二元数组有 k 个运算符，每个运算符有 2 个整数 A[i].x, A[i].y，你可通过改变矩阵网格中的A[i].x]，[A[i].y] 来将其由海洋改为岛屿。请在每次运算后，返回矩阵中岛屿的数量。

 注意事项

0 代表海，1 代表岛。如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

您在真实的面试中是否遇到过这个题？ Yes
样例
给定 n = 3, m = 3， 二元数组 A = [(0,0),(0,1),(2,2),(2,1)].

返回 [1,1,2,2].

public class Jdbct {

     class Point {
              int x;
              int y;
              Point() { x = 0; y = 0; }
              Point(int a, int b) { x = a; y = b; }
         }
     public List<Integer> numIslands2(int m, int n, Point[] operators) {
         List<Integer> result = new ArrayList<>();
         if (operators == null || operators.length == 0) {
             return result;
         }
         int[][] island = new int[m][n];
         Set<Integer> set = new HashSet<>();
         for (int i = 0; i < m; i++) {
             for (int j = 0; j < n; j++) {
                 set.add(i * n + j);
             }
         }
         int[] dx = {-1, 1, 0, 0};
         int[] dy = {0, 0, -1, 1};
         UnionFind uf = new UnionFind(set);
         int count = 0;
         for (Point point : operators) {
             int x = point.x;
             int y = point.y;
             if (island[x][y] == 0) {
                 island[x][y] = 1;
                 count++;
                 for (int i = 0; i < 4; i++) {
                     int newX = x + dx[i];
                     int newY = y + dy[i];
                     if (newX >= 0 && newX < m && newY >= 0 && newY < n && island[newX][newY] == 1){
                         int x_father = uf.find(x * n + y);
                         int newX_father = uf.find(newX * n + newY);
                         if (x_father != newX_father) {
                             count--;
                             uf.union(x * n + y, newX * n + newY);
                         }
                     }
                 }
             }
             result.add(count);
         }
         return result;
     }

}
class UnionFind {
    private Map<Integer, Integer> map = new HashMap<>();
    
    public UnionFind(Set<Integer> set) {
        for (int t : set) {
            map.put(t, t);
        }
    }
    
    public int find(int x) {
        int r = x;
        if (r != map.get(r)) {
            r = map.get(r);
        }
        
        int i = x, j;
        while (i != r) {
            j = map.get(i);
            map.put(i, r);
            i = j;
        }
        return r;
    }
    
    public void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            map.put(fx, fy);
        }
    }
}

5 Surrounded Regions

    public void surroundedRegions(char[][] board)
    {
        // Write your code here
        if (board == null || board.length <= 1 || board[0].length <= 1)
        {
            return;
        }
        for (int i = 0; i < board[0].length; i++)
        {
            fill(board, 0, i);
            fill(board, board.length - 1, i);
        }
        for (int i = 0; i < board.length; i++)
        {
            fill(board, i, 0);
            fill(board, i, board[0].length - 1);
        }
        for (int i = 0; i < board.length; i++)
        {
            for (int j = 0; j < board[0].length; j++)
            {
                if (board[i][j] == 'O')
                {
                    board[i][j] = 'X';
                }
                else if (board[i][j] == '#')
                {
                    board[i][j] = 'O';
                }
            }
        }
    }
    public void fill(char[][] board, int i, int j)
    {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {
            return;
        }
        board[i][j] = '#';
        fill(board, i + 1, j);
        fill(board, i - 1, j);
        fill(board, i, j - 1);
        fill(board, i, j + 1);
    }

6 Graph Valid Tree

    public boolean validTree(int n, int[][] edges) {
        // Write your code here
        if (n == 0) {
            return false;
        }
        if (edges.length != n - 1) {
            return false;
        }

        Union u = new Union(n);
        for (int i = 0; i < edges.length; i++){
            if (u.find(edges[i][0]) == u.find(edges[i][1])){
                return false;
            }
            u.union(edges[i][0], edges[i][1]);
        }
        return true;
    }
}
class Union{
    HashMap<Integer, Integer> map = new HashMap<>();
    
    public Union(int n){
        for (int i = 0; i < n; i++){
            map.put(i, i);
        }
    }
    public int find(int x){
        int r = map.get(x);
        
        while (r != map.get(r)){
            r = map.get(r);
        }
        
        int j = x, i;
        while (r != j){
            i = map.get(j);
            map.put(j, r);
            j = i;
        }
        return r;
    }
    
    public void union(int x, int y){
        int fx = find(x), fy = find(y);
        if (fx != fy){
            map.put(x, fy);
        }
    }
}

Trie   快速找到一个元素，一个字母一个字母查找

1 Implement Trie

  class TrieNode {  
        public TrieNode[] children = new TrieNode[26];  
        public String item = "";  
          
        // Initialize your data structure here.  
        public TrieNode() {  
        }  
    }  
      
    class Trie {  
        private TrieNode root;  
      
        public Trie() {  
            root = new TrieNode();  
        }  
      
        // Inserts a word into the trie.  
        public void insert(String word) {  
            TrieNode node = root;  
            for (char c : word.toCharArray()) {  
                if (node.children[c - 'a'] == null) {  
                    node.children[c - 'a'] = new TrieNode();  
                }  
                node = node.children[c - 'a'];  
            }  
            node.item = word;  
        }  
      
        // Returns if the word is in the trie.  
        public boolean search(String word) {  
            TrieNode node = root;  
            for (char c : word.toCharArray()) {  
                if (node.children[c - 'a'] == null) return false;  
                node = node.children[c - 'a'];  
            }  
            return node.item.equals(word);  
        }  
      
        // Returns if there is any word in the trie  
        // that starts with the given prefix.  
        public boolean startsWith(String prefix) {  
            TrieNode node = root;  
            for (char c : prefix.toCharArray()) {  
                if (node.children[c - 'a'] == null) return false;  
                node = node.children[c - 'a'];  
            }  
            return true;  
        }  
    }  

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean hasWord = false;
    public void insert(String word, int index) {
        if (word.length() == index) {
            this.hasWord = true;
            return;
        }
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            children[pos] = new TrieNode();
        }
        children[pos].insert(word, index + 1);
    }
    public TrieNode find(String word, int index) {
        if (word.length() == index) {
            return this;
        }
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            return null;
        }
        return children[pos].find(word, index + 1);
    }
}
class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        root.insert(word, 0);
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = root.find(word, 0);
        return (node != null && node.hasWord);
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = root.find(prefix, 0);
        return node != null;
    }
}

2 Word Search

   public boolean exist(char[][] board, String word) 
    {
        // write your code here
        if (word == null || word.length() == 0)
        {
            return true;
        }
        if (board == null || board.length == 0 || board[0].length == 0)
        {
            return false;
        }
        for (int i = 0; i < board.length; i++)
        {
            for (int j = 0; j < board[0].length; j++)
            {
                if (check(board, word, new boolean[board.length][board[0].length], 0, i, j))
                {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean check(char[][] board, String word, boolean[][] bs, int len, int i, int j) {
        // TODO Auto-generated method stub
        if (len == word.length())
        {
            return true;
        }
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || bs[i][j]|| board[i][j] != word.charAt(len))
        {
            return false;
        }
        bs[i][j] = true;
        boolean res = check(board, word, bs, len + 1, i + 1, j) ||
                check(board, word, bs, len + 1, i - 1, j) ||
                check(board, word, bs, len + 1, i, j + 1) ||
                check(board, word, bs, len + 1, i, j - 1);
        bs[i][j] = false;
        return res;
    }

3 Word Search II

public class Solution {

    Set<String> res = new HashSet<String>();
    int m = 0, n = 0;
    Trie trie = new Trie();
    public List<String> findWords(char[][] board, String[] words) {
        m = board.length; n = board[0].length;
        for (String s : words){
            trie.insert(s);
        }
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                help(board, visited, "", i, j);
            }
        }
        return new ArrayList<>(res);
    }
    public void help(char[][] board, boolean[][] visited, String item, int i, int j){
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) return;
        item = item + board[i][j];
        if (!trie.startsWith(item)) return;
        if (trie.search(item)) res.add(item);
        visited[i][j] = true;
        help(board, visited, item, i - 1, j);
        help(board, visited, item, i + 1, j);
        help(board, visited, item, i, j - 1);
        help(board, visited, item, i, j + 1);
        visited[i][j] = false;
    }
}
    class TrieNode {  
        public TrieNode[] children = new TrieNode[26];  
        public String item = "";  
          
        // Initialize your data structure here.  
        public TrieNode() {  
        }  
    }  
      
    class Trie {  
        private TrieNode root;  
      
        public Trie() {  
            root = new TrieNode();  
        }  
      
        // Inserts a word into the trie.  
        public void insert(String word) {  
            TrieNode node = root;  
            for (char c : word.toCharArray()) {  
                if (node.children[c - 'a'] == null) {  
                    node.children[c - 'a'] = new TrieNode();  
                }  
                node = node.children[c - 'a'];  
            }  
            node.item = word;  
        }  
      
        // Returns if the word is in the trie.  
        public boolean search(String word) {  
            TrieNode node = root;  
            for (char c : word.toCharArray()) {  
                if (node.children[c - 'a'] == null) return false;  
                node = node.children[c - 'a'];  
            }  
            return node.item.equals(word);  
        }  
      
        // Returns if there is any word in the trie  
        // that starts with the given prefix.  
        public boolean startsWith(String prefix) {  
            TrieNode node = root;  
            for (char c : prefix.toCharArray()) {  
                if (node.children[c - 'a'] == null) return false;  
                node = node.children[c - 'a'];  
            }  
            return true;  
        }  
    }  

 4 Add and Search Word

public class WordDictionary {

    private TrieNode root = new TrieNode();
    // Adds a word into the data structure.
    public void addWord(String word) {
        // Write your code here
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null){
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.hasWord = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        // Write your code here
        return find(word, 0, root);
    }
    public boolean find(String word, int index, TrieNode now){
        if (index == word.length()){
            return now.hasWord;
        }
        char c = word.charAt(index);
        if (c == '.'){
            for (int i = 0; i < 26; i++){
                if (now.children[i] != null){
                    if (find(word, index + 1, now.children[i])){
                        return true;
                    }
                }
            }
            return false;
        } else if (now.children[c - 'a'] != null){
            return find(word, index + 1, now.children[c - 'a']);
        } else {
            return false;
        }
    }
}

class TrieNode{
    public TrieNode[] children;
    public boolean hasWord;
    public TrieNode(){
        children = new TrieNode[26];
        hasWord = false;
    }
}

Scan-Line  区间拆分

1 Number of Airplane in the sky

class Solution {
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) { 
        // write your code here
        List<Point> list = new ArrayList<Point>();
        for (Interval i : airplanes){
            list.add(new Point(i.start, 1));
            list.add(new Point(i.end, 0));
        }
        Collections.sort(list, new Comparator<Point>() {
            public int compare(Point p1, Point p2) {
                if (p1.time == p2.time) {
                    return p1.flag - p2.flag;
                }
                else {
                    return p1.time - p2.time;
                }
            }
        });
        int count = 0, res = 0;
        for (Point p : list){
            if (p.flag == 1){
                count++;
            } else{
                count--;
            }
            res = Math.max(count, res);
        }
        return res;
    }
    
    
}
class Point{
    int time;
    int flag;
    Point(int time, int flag){
        this.time = time;
        this.flag = flag;
    }
}

heap定义：

 java的 PriorityQueue是一个小顶堆，用于找最大前K个严肃。sort可重写。在本博客下面一个地方有详细介绍。

1 Trapping Rain Water

public int trapRainWater(int[] heights) 
{
    if (heights == null || heights.length == 0)
    {
        return 0;
    }
    int res = 0;
    int l = 0;
    int r = heights.length - 1;
    int left_height = heights[l];
    int right_height = heights[r];
    while (l < r) {
        if (left_height < right_height) {
            l++;
            if (left_height > heights[l]) {
                res += left_height - heights[l];
            } else {
                left_height = heights[l];
            }
        } else {
            r--;
            if (right_height > heights[r]) {
                res += right_height - heights[r];
            } else {
                right_height = heights[r];
            }
        }
    }
    return res;
}

2 Trapping Rain Water II

public class Solution {
    /**
     * @param heights: a matrix of integers
     * @return: an integer
     */
    class Point{
        int x, y, h;
        public Point(int x, int y, int h) {
            this.x = x; this.y = y; this.h = h;
        }
    }
    public int trapRainWater(int[][] heights) {
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return 0;
        }
        int m = heights.length;
        int n = heights[0].length;
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        int res = 0;
        Queue<Point> q = new PriorityQueue<>((p1, p2)->p1.h - p2.h);
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < n; i++) {
            q.add(new Point(0, i, heights[0][i]));
            visited[0][i] = true;
            q.add(new Point(m - 1, i, heights[m - 1][i]));
            visited[m - 1][i] = true;           
        }
         for (int i = 0; i < m; i++) {
            q.add(new Point(i, 0, heights[i][0]));
            visited[i][0] = true;
            q.add(new Point(i, n -1, heights[i][n - 1]));
            visited[i][n - 1] = true;           
        }
        while (!q.isEmpty()) {
            Point p = q.poll();
            for (int k = 0; k < 4; k++) {
                int newX = p.x + dx[k];
                int newY = p.y + dy[k];
                if (newX < 0 || newX >= m || newY < 0 || newY >= n || visited[newX][newY]) {
                    continue;
                }
                visited[newX][newY] = true;
                q.add(new Point(newX, newY, Math.max(p.h, heights[newX][newY])));
                res += Math.max(0, p.h - heights[newX][newY]);
            }
        }
        return res;
    }     
}

 3 Building Outline

    public List<int[]> getSkyline(int[][] build) {
        List<int[]> res = new ArrayList<>();
        List<int[]> point = new ArrayList<>();
        for (int i = 0; i < build.length; i++){
            point.add(new int[]{build[i][0], build[i][2]});
            point.add(new int[]{build[i][1], -build[i][2]});
        }
        Collections.sort(point, (a,b)->{
            if (a[0] == b[0]) return b[1] - a[1];
            return a[0] - b[0];
        });
        Queue<Integer> q = new PriorityQueue<>((a,b)->(b - a));
        int pre = 0, cur = 0;
        for (int[] p : point){
            if (p[1] > 0) {
                q.offer(p[1]);
                cur = q.peek();
            } else {
                q.remove(-p[1]);
                cur = q.isEmpty() ? 0 : q.peek();
            }
            if (pre != cur){
                res.add(new int[]{p[0], cur});
                pre = cur;
            }
        }
        return res;
    }

 4 Heapify

   private void siftdown(int[] A, int k) {

        while (k < A.length) {

            int smallest = k;

            if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {

                smallest = k * 2 + 1;

            }

            if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {

                smallest = k * 2 + 2;

            }

            if (smallest == k) {

                break;

            }

            int temp = A[smallest];

            A[smallest] = A[k];

            A[k] = temp;

            

            k = smallest;

        }

    }

    

    public void heapify(int[] A) {

        for (int i = A.length / 2; i >= 0; i--) {

            siftdown(A, i);

        } // for

    }

5 Data Stream Median

    public int[] medianII(int[] nums) {
        // write your code here
        Comparator<Integer> comp = new Comparator<Integer>(){
            public int compare(Integer left, Integer right) {
                return right - left;
            }  
        };
        int len = nums.length;
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(comp);
        int[] res = new int[len];
        res[0] = nums[0];
        maxQ.add(nums[0]);
        for (int i = 1; i < len; i++) {
            int x = maxQ.peek();
            if (nums[i] < x) {
                maxQ.add(nums[i]);
            } else {
                minQ.add(nums[i]);
            }
            if (maxQ.size() > minQ.size() + 1){
                minQ.add(maxQ.poll());
            } else if (minQ.size() > maxQ.size()){
                maxQ.add(minQ.poll());
            }
            res[i] = maxQ.peek();
        }
        return res;
    }

6 Sliding Window Median   拆成两个步骤  1 加入一个元素，2删除一个元素， 求中位数

    public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
        // write your code here
        ArrayList<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0 || k <= 0) return res;
        PriorityQueue<Integer> max = new PriorityQueue<>((a,b)->(b - a));
        PriorityQueue<Integer> min = new PriorityQueue<>();
        int mid = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (i != 0) {
                if (nums[i] > mid) {
                    min.add(nums[i]);
                } else {
                    max.add(nums[i]);
                }
            }
            if (i >= k) {
                if (mid == nums[i - k]) {
                    if (max.size() > 0) {
                        mid = max.poll();
                    } else if (min.size() > 0) {
                        mid = min.poll();
                    }
                } else if (mid > nums[i - k]) {
                    max.remove(nums[i - k]);
                } else {
                    min.remove(nums[i - k]);
                }
            }
            while (max.size() > min.size()) {
                min.add(mid);
                mid = max.poll();
            }
            while (min.size() > max.size() + 1) {
                max.add(mid);
                mid = min.poll();
            }
            if (i >= k - 1) {
                res.add(mid);
            }
        }
        return res;
    }

7 sliding-window-maximum

    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        // write your code here
        ArrayList<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0 || k <= 0) {
            return res;
        }
        Deque<Integer> q = new ArrayDeque<Integer>();
        for (int i = 0; i < nums.length; i++) {
            while (!q.isEmpty() && nums[i] > q.peekLast()){
                q.pollLast();
            }
            q.offer(nums[i]);
            if (i > k - 1 && q.peekFirst() == nums[i - k]) {
                q.pollFirst();
            }
            if (i >= k - 1) {
                res.add(q.peekFirst());
            }
        }
        r