Day04

算法每日一题

原题链接：https://leetcode.cn/problems/maximal-square/description/?envType=problem-list-v2&envId=2cktkvj
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
    if (matrix.length === 0 || matrix[0].length === 0) return 0;

    let m = matrix.length, n = matrix[0].length;
    let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    let max = 0;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] === '1') {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
    }

    return max * max;
};

动态规划（Dynamic Programming, DP）是一种用于解决复杂问题的方法，通过将问题分解为更小的子问题并存储这些子问题的解来避免重复计算。它通常用于优化问题，特别是那些具有重叠子问题和最优子结构性质的问题。

基本步骤
1.定义子问题：将原问题分解为更小的子问题。
2.推导状态转移方程：找到子问题之间的关系，通常是通过递归公式。
3.确定边界条件：定义最小的子问题的解。
4.自底向上计算：从边界条件开始，逐步计算较大的子问题的解，直到得到原问题的解。

在这个问题中，我们使用一个dp数组来存储以当前位置为右下顶点的最大正方形的边长。假设我们正在处理一个二维矩阵，其中每个元素要么是0要么是1。我们的目标是找到矩阵中只包含1的最大正方形，并返回其面积。

具体来说，如果当前元素为1，那么我们需要考虑它左边、上边和左上角三个方向的dp值，因为这三个方向的dp值分别代表以这些位置为右下顶点的最大正方形的边长。为了使以当前位置为右下顶点的正方形尽可能大，当前元素的dp值应该是这三个方向的最小值加1。也就是说，如果左边、上边和左上角的dp值分别是a, b, c，那么当前元素的dp值就是min(a, b, c) + 1。

这样，我们就得到了状态转移方程：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1。

通过这个状态转移方程，我们可以从矩阵的左上角开始，逐步计算每个位置的dp值，直到遍历完整个矩阵。最终，dp数组中最大的值就是矩阵中只包含1的最大正方形的边长，其面积就是该边长的平方。

webpack

Webpack 5 内置了对图片等资源文件的处理功能，可以通过配置 asset 模块来实现当图片小于一定大小时将其打包为 Base64 格式的 Data URL。这样做的好处是减少了 HTTP 请求的数量，虽然会稍微增加文件的体积。

{
        test: /\.(png|jpg|gif)$/,
        type: "asset",
        parser: {
          dataUrlCondition: {
            maxSize: 8 * 1024, // 小于8kb时进行转化1. 
        }
    }
}