题目描述：
 
我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？
 
思路：
 
由题目看出，f(n) = f(n - 1) + f(n - 2).
 
参考代码：
 
递归法：
 
public static long RectCover1(int target) {
   if(target < 3)return target;
   return RectCover(target - 1) + RectCover(target - 2);
  }
 
非递归
 
public static long RectCover(int target) {
   if(target < 3)return target;
   long pre1 = 1;
   long pre2 = 2;
   
   for(int i = 3; i<= target; i++){
    long sum = pre1 + pre2;
    pre1 = pre2;
    pre2 = sum;
   }
   return pre2;
  }

力扣题目地址：https://leetcode-cn.com/problems/rectangle-overlap/
 
首先看题目：
 矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
 
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
 
给出两个矩形，判断它们是否重叠并返回结果。
 
示例：
 
示例 1：
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

示例 2：
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false
 
解决思路：
 方法一：图解法
 这个题目一拿到手，我就觉得这是一个非常简单的数学问题：在二维坐标轴上，一个数组给定两个坐标确定一个矩形；判断两个数组代表的矩形是否重叠。只有在第二个矩形的（x4，y4）坐标在第一个矩形的（x1，y1）的上方，并且第二个矩形的（x3，y3）坐标在第一个矩形的（x2，y2）的下方时，才会出现重叠的情况。这题目其实只要拿出纸笔，在纸上画出来就能很好的理解它了。
 
方法二：检查区域法
 我们将两个矩形的两个坐标连成的线段，分别映射到x轴和y轴上；我们会发现，如果这两个矩形存在重叠部分，那么x轴和y轴的映射线段必定会相交。所以我们可以根据坐标点来判断这两条线段是否相交。
 
代码实现：
 
	/**
     * 方法一：图解法
     * https://leetcode-cn.com/problems/rectangle-overlap/
     * @param rec1
     * @param rec2
     * @author Geyuxuan 2020-03-18 20:53:28
     * @return boolean
     */
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        if(rec2[2]>rec1[0] && rec2[3]>rec1[1] && rec2[0]<rec1[2] && rec2[1]<rec1[3]){
            return true;
        }
        return false;
    }

	/**
     * 方法二：检查区域法
     * https://leetcode-cn.com/problems/rectangle-overlap/
     * @param rec1
     * @param rec2
     * @author Geyuxuan 2020-03-18 20:53:28
     * @return boolean
     */
    public boolean isRectangleOverlap1(int[] rec1, int[] rec2) {
        if(Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]) && Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1])){
            return true;
        }
        return false;
    }
 
不忘初心，砥砺前行。

题目 矩形
 
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
 
两个相邻元素间的距离为 1 。
 
 
 
题解 广度优先搜索
 
本题的本质就是寻找离1最近的0，那么就可以从0出发进行搜索，一开始利用一个队列把所有的0都压入队列，并把1的位置改为-1表示未访问过。
 如果遇到符合要求的：表示它为当前距离+1
 
if(pos_x >=0 && pos_x < row && pos_y >= 0 &&
      pos_y < col && mat[pos_x][pos_y] == -1){
   mat[pos_x][pos_y] = mat[x][y] + 1;
   q.push(make_pair(pos_x, pos_y));
}
 
完整代码如下：
 
class Solution {
public:
    const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int row = mat.size();
        int col = mat[0].size();
        queue<pair<int, int>> q;
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(mat[i][j] == 0){
                    q.push(make_pair(i, j));
                }
                else{
                    mat[i][j] = -1;
                }
            }
        }
        while(!q.empty()){
            auto [x, y] = q.front();
            q.pop();
            for(int i = 0; i < 4; ++i){
                int pos_x = x + dir[i][0];
                int pos_y = y + dir[i][1];
                if(pos_x >=0 && pos_x < row && pos_y >= 0 && pos_y < col 
                      && mat[pos_x][pos_y] == -1){
                    mat[pos_x][pos_y] = mat[x][y] + 1;
                    q.push(make_pair(pos_x, pos_y));
                }
            }
        }
        return mat;
    }
};
 
题目 地图分析
 
你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。
 
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
 
如果网格上只有陆地或者海洋，请返回 -1。
 
 
题解 广度优先搜索
 
上一题的本质是寻找离1最近的0，这一题刚好反过来，寻找离1最近的0的最远距离，则与上一题处理思路完全一样：
 
class Solution {
public:
   const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int maxDistance(vector<vector<int>>& grid) {
        queue<pair<int, int>> q;
        int row = grid.size();
        int col = grid[0].size();
        int cnt = 0;
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(grid[i][j] == 1){
                    q.push({i, j});
                    cnt++;
                    grid[i][j] = 0;
                }
                else{
                    grid[i][j] = -1;
                }
            }
        }
        if(cnt == 0 || cnt == row * col)
            return -1;
        int x, y;
        while(!q.empty()){
            x = q.front().first;
            y = q.front().second;
            q.pop();
            for(int i = 0; i < 4; ++i){
                int pos_x = x + dir[i][0];
                int pos_y = y + dir[i][1];
                if(pos_x >=0 && pos_x < row && pos_y >= 0 &&
                     pos_y < col && grid[pos_x][pos_y] == -1){
                    grid[pos_x][pos_y] = grid[x][y] + 1;
                    q.push({pos_x, pos_y});                   
                }
            }
        }
        //int res;
        //for(int i = 0; i < row; ++i){
          //  res = max(res,*max_element(grid[i].begin(), grid[i].end()));
        //}
        return grid[x][y];
    }
};
 
总结
 
多思考，多学习！

最大矩形
 
题目描述：
 
 
 

  给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 
 
 

  提示：
 
 
 

     rows == matrix.length
 
 
 

     cols == matrix[0].length
 
 
 

     0 <= row, cols <= 200
 
 
 

     matrix[i][j] 为 '0' 或 '1'
 
 
 
题目链接
 
示例
 
 
 
 

  输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 
 
 

  输出：6
 
 
 

  解释：最大矩形如上图所示。
 
 
 
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if(row == 0) return 0;
        int col = matrix[0].length;
        // 初始化
        int[][] heights = new int[row][col];
        for(int i = 0 ; i<col ; i++){
            for(int j = row-1 ; j>=0 ; j--){
                if(matrix[j][i] == '1'){
                    heights[j][i] = ((j == row-1)?0:(heights[j+1][i]))+1;
                }
            }
        }
        int max = 0;
        for(int i = 0 ; i<row ; i++){ // 遍历每一行
            int temp = largestRectangleArea(heights[i]);
            max = (max>temp)?max:temp;
        }
        return max;
    }
    private int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if(len == 0) return 0;
        if (len == 1) return heights[0];

        int result = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            while (!stack.empty() && heights[i] < heights[stack.peek()]) { // 如果当前遍历下标的高度严格小于下标为栈顶的元素高度
                int curHeight = heights[stack.pop()];
                while (!stack.empty() && heights[stack.peek()] == curHeight) { // 相等情况下去重
                    stack.pop();
                }

                int curWidth;
                if (stack.empty()) {
                    curWidth = i;
                } else {
                    curWidth = i - stack.peek() - 1;
                }
                result = Math.max(result, curHeight * curWidth);
            }
            stack.push(i);
        }
        // 最终处理
        while (!stack.empty()) {
            int curHeight = heights[stack.pop()];
            while (!stack.empty() && heights[stack.peek()] == curHeight) {
                stack.pop();
            }
            int curWidth;
            if (stack.empty()) {
                curWidth = len;
            } else {
                curWidth = len - stack.peek() - 1;
            }
            result = Math.max(result, curHeight * curWidth);
        }
        return result;
    }
}
 
该题本质上就是单调栈的应用，读者可以首先理解完该题，再来解决此题。
 首先我们需要进行预处理，即对matrix矩阵每一列的连续1的个数记录到heights矩阵中，最后以一行一行的顺序进行单调栈操作，通过每一行的最大的矩形面积更新全局最大矩形面积。读者可以试着在草稿纸上模拟，详细请看代码。