关于算法:为何我刷了很多遇到新的题还是唯唯诺诺无法重拳出击

为何我刷了很多题，遇到新的题还是气宇轩昂，无奈重拳出击？为何一看就会一些就废？这其中又暗藏着怎么的机密？到底是道德的沦丧还是兽性的扭曲？欢送收看本期的 走出迷信 特地栏目。

明天给大家带来了 三位重量级选手，一位体重 98 公斤，一位体重 100 公斤，还有一位体重 98 斤，明天 lucifer 就带大家用同样的招式 KO 他们三位。

https://leetcode-cn.com/probl…

给定 n 个非负整数，用来示意柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。

求在该柱状图中，可能勾画进去的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中暗影局部为所能勾画出的最大矩形面积，其面积为 10 个单位。

示例：输出：[2,1,5,6,2,3]
输入：10

阿里
腾讯
百度
字节

枯燥栈

咱们暴力尝试 所有可能的矩形 。因为矩阵是二维图形，我咱们能够应用 左右两个端点来惟一确认一个矩阵。因而咱们应用双层循环枚举所有的可能性即可。而矩形的面积等于（右端点坐标 - 左端点坐标 + 1) * 最小的高度，最小的高度咱们能够在遍历的时候顺便求出。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n, ans = len(heights), 0
        if n != 0:
            ans = heights[0]
        for i in range(n):
            height = heights[i]
            for j in range(i, n):
                height = min(height, heights[j])
                ans = max(ans, (j - i + 1) * height)
        return ans

复杂度剖析

工夫复杂度：$O(N^2)$
空间复杂度：$O(1)$

咱们依然暴力尝试 所有可能的矩形。只不过咱们这一次从核心向两边进行扩大。对于每一个 i，咱们计算出其右边第一个高度小于它的索引 p，同样地，计算出左边第一个高度小于它的索引 q。那么以 i 为最低点可能形成的面积就是(q - p - 1) * heights[i]。这种算法毫无疑问也是正确的。咱们证实一下，假如 f(i) 示意求以 i 为最低点的状况下，所能造成的最大矩阵面积。那么原问题转化为max(f(0), f(1), f(2), ..., f(n - 1))。

具体算法如下：

咱们应用 l 和 r 数组。l[i] 示意右边第一个高度小于它的索引，r[i] 示意左边第一个高度小于它的索引。
咱们从前往后求出 l，再从后往前计算出 r。
再次遍历求出所有的可能面积，并取出最大的。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        l, r, ans = [-1] * n, [n] * n, 0
        for i in range(1, n):
            j = i - 1
            while j >= 0 and heights[j] >= heights[i]:
                j -= 1
            l[i] = j
        for i in range(n - 2, -1, -1):
            j = i + 1
            while j < n and heights[j] >= heights[i]:
                j += 1
            r[i] = j
        for i in range(n):
            ans = max(ans, heights[i] * (r[i] - l[i] - 1))
        return ans

复杂度剖析

工夫复杂度：$O(N^2)$
空间复杂度：$O(N)$

实际上咱们内层循环没必要一步一步挪动，咱们能够间接将j -= 1 改成 j = l[j], j += 1 改成 j = r[j]。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        l, r, ans = [-1] * n, [n] * n, 0

        for i in range(1, n):
            j = i - 1
            while j >= 0 and heights[j] >= heights[i]:
                j = l[j]
            l[i] = j
        for i in range(n - 2, -1, -1):
            j = i + 1
            while j < n and heights[j] >= heights[i]:
                j = r[j]
            r[i] = j
        for i in range(n):
            ans = max(ans, heights[i] * (r[i] - l[i] - 1))
        return ans

复杂度剖析

工夫复杂度：$O(N)$
空间复杂度：$O(N)$

实际上，读完第二种办法的时候，你应该留神到了。咱们的外围是求右边第一个比 i 小的和左边第一个比 i 小的。如果你相熟枯燥栈的话，那么应该会想到这是非常适合应用枯燥栈来解决的场景。

从左到右遍历柱子，对于每一个柱子，咱们想找到第一个高度小于它的柱子，那么咱们就能够应用一个枯燥递增栈来实现。如果柱子大于栈顶的柱子，那么阐明不是咱们要找的柱子，咱们把它塞进去持续遍历，如果比栈顶小，那么咱们就找到了第一个小于的柱子。对于栈顶元素，其左边第一个小于它的就是以后遍历到的柱子，右边第一个小于它的就是栈中下一个要被弹出的元素 ，因而以以后栈顶为最小柱子的面积为 以后栈顶的柱子高度 * (以后遍历到的柱子索引 – 1 – (栈中下一个要被弹出的元素索引 + 1) + 1)，化简一下就是 以后栈顶的柱子高度 * (以后遍历到的柱子索引 – 栈中下一个要被弹出的元素索引 – 1)。

这种办法只须要遍历一次，并用一个栈。因为每一个元素最多进栈出栈一次，因而工夫和空间复杂度都是 $O(N)$。

为了对立算法逻辑，缩小边界解决，我在 heights 首尾增加了两个哨兵元素，这样咱们能够保障所有的柱子都会出栈。

代码反对：Python,CPP

Python Code:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n, heights, st, ans = len(heights), [0] + heights + [0], [], 0
        for i in range(n + 2):
            while st and heights[st[-1]] > heights[i]:
                ans = max(ans, heights[st.pop(-1)] * (i - st[-1] - 1))
            st.append(i)
        return ans

CPP Code:

class Solution {
public:
    int largestRectangleArea(vector<int>& A) {A.push_back(0);
        int N = A.size(), ans = 0;
        stack<int> s;
        for (int i = 0; i < N; ++i) {while (s.size() && A[s.top()] >= A[i]) {int h = A[s.top()];
                s.pop();
                int j = s.size() ? s.top() : -1;
                ans = max(ans, h * (i - j - 1));
            }
            s.push(i);
        }
        return ans;
    }
};

复杂度剖析

工夫复杂度：$O(N)$
空间复杂度：$O(N)$

2020-05-30 更新：

有的观众反馈看不懂为啥须要两个哨兵。其实开端的哨兵就是为了将栈清空，避免遍历实现栈中还有没参加运算的数据。

而后面的哨兵有什么用呢？我这里把下面代码进行了拆解：

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n, heights, st, ans = len(heights),[0] + heights + [0], [], 0
        for i in range(n + 2):
            while st and heights[st[-1]] > heights[i]:
                a = heights[st[-1]]
                st.pop()
                # 如果没有后面的哨兵，这里的 st[-1] 可能会越界。ans = max(ans, a * (i - 1 - st[-1]))
            st.append(i)
        return ans

42.trapping-rain-water

https://leetcode-cn.com/probl…

给定一个仅蕴含 0 和 1 的二维二进制矩阵，找出只蕴含 1 的最大矩形，并返回其面积。

示例：

输出：

[["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

输入：6

枯燥栈

阿里
腾讯
百度
字节

我在【84. 柱状图中最大的矩形】多种办法（Python3）应用了多种办法来解决。然而在这道题，咱们依然能够应用齐全一样的思路去实现。本题解是基于那道题的题解来进行的。

拿题目给的例子来说：

[["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

咱们逐行扫描失去 84. 柱状图中最大的矩形 中的 heights 数组：

这样咱们就能够应用84. 柱状图中最大的矩形 中的解法来进行了，这里咱们应用枯燥栈来解。

上面的代码间接将 84 题的代码封装成 API 调用了。

代码反对：Python

Python Code:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n, heights, st, ans = len(heights), [0] + heights + [0], [], 0
        for i in range(n + 2):
            while st and heights[st[-1]] > heights[i]:
                ans = max(ans, heights[st.pop(-1)] * (i - st[-1] - 1))
            st.append(i)

        return ans
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        if m == 0: return 0
        n = len(matrix[0])
        heights = [0] * n
        ans = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "0":
                    heights[j] = 0
                else:
                    heights[j] += 1
            ans = max(ans, self.largestRectangleArea(heights))
        return ans

复杂度剖析

工夫复杂度：$O(M * N)$
空间复杂度：$O(N)$

https://leetcode-cn.com/probl…

在一个由 0 和 1 组成的二维矩阵内，找到只蕴含 1 的最大正方形，并返回其面积。示例:

输出:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输入: 4

动静布局
递归

阿里
腾讯
百度
字节

看到题看起来和下面的题目相似，只不过把长方形限定为了正方形嘛。

合乎直觉的做法是暴力求解处所有的正方形，逐个计算面积，而后记录最大的。这种工夫复杂度很高。

咱们思考应用动静布局，咱们应用 dpi 示意以 matrixi 为右下角的顶点的能够组成的最大正方形的边长。
那么咱们只须要计算所有的 i，j 组合，而后求出最大值即可。

咱们来看下 dpi 怎么推导。首先咱们要看 matrixi, 如果 matrixi 等于 0，那么就不必看了，间接等于 0。
如果 matrixi 等于 1，那么咱们将 matrix[i 别离往上和往左进行延长，直到碰到一个 0 为止。

如图 dp3 的计算。matrix3 等于 1，咱们别离往上和往左进行延长，直到碰到一个 0 为止，下面长度为 1，右边为 3。
dp2 等于 1（之前曾经计算好了），那么其实这里的瓶颈在于三者的最小值, 即Min(1, 1, 3), 也就是1。那么 dp3 就等于
Min(1, 1, 3) + 1。

dpi – 1 咱们间接拿到，要害是 往上和往左进行延长 , 最直观的做法是咱们内层加一个循环去做就好了。
然而咱们仔细观察一下，其实咱们基本不须要这样算。咱们能够间接用 dpi – 1 和 dpi。
具体就是Min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1。

事实上，这道题还有空间复杂度 O(N)的解法，其中 N 指的是列数。
大家能够去这个 leetcode 探讨看一下。

DP
递归公式能够利用 dpi – 1 和 dpi 的计算结果，而不必从新计算
空间复杂度能够升高到 O(n), n 为列数

代码反对：Python，JavaScript：

Python Code：

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        res = 0
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 if matrix[i - 1][j - 1] == "1" else 0
                res = max(res, dp[i][j])
        return res ** 2

JavaScript Code：

/*
 * @lc app=leetcode id=221 lang=javascript
 *
 * [221] Maximal Square
 */
/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {if (matrix.length === 0) return 0;
  const dp = [];
  const rows = matrix.length;
  const cols = matrix[0].length;
  let max = Number.MIN_VALUE;

  for (let i = 0; i < rows + 1; i++) {if (i === 0) {dp[i] = Array(cols + 1).fill(0);
    } else {dp[i] = [0];
    }
  }

  for (let i = 1; i < rows + 1; i++) {for (let j = 1; j < cols + 1; j++) {if (matrix[i - 1][j - 1] === "1") {dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
        max = Math.max(max, dp[i][j]);
      } else {dp[i][j] = 0;
      }
    }
  }

  return max * max;
};

复杂度剖析

工夫复杂度：$O(M * N)$，其中 M 为行数，N 为列数。
空间复杂度：$O(M * N)$，其中 M 为行数，N 为列数。

当然能够！lucifer 我就专门给大家改写了一下，间接将下面的代码复制过去，改了一行就 AC 了。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n, heights, st, ans = len(heights), [0] + heights + [0], [], 0
        for i in range(n + 2):
            while st and heights[st[-1]] > heights[i]:
                # 就只改了上面这一行
                ans = max(ans, min(heights[st.pop()], (i - st[-1] - 1)) ** 2)
            st.append(i)

        return ans

    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        heights = [0] * n
        ans = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "0":
                    heights[j] = 0
                else:
                    heights[j] += 1
            ans = max(ans, self.largestRectangleArea(heights))
        return ans

下面三道题我都用的是 largestRectangleArea 的外围逻辑，基本上调用下略微改改就完事了。对于 largestRectangleArea 的解法最显著的莫过于平方级别的暴力，可如果你仔细分析就发现咱们能够通过 指针不回溯 达到升高复杂度的成果。而这里的指针不回溯能够是枯燥栈，也能够是我给的双指针数组办法。不论用的哪种，区别的只是战术，战略思想是一样的。大家做题的时候也要重视策略，训练战术。

你说这招是不是很好使？学习算法不可贪多，不然嚼不烂。当你细细咀嚼后会发现，其实算法的思维和套路还真不多，至多应酬大部分的面试和 OJ 题目不成问题。

关于算法:为何我刷了很多遇到新的题还是唯唯诺诺无法重拳出击

第一位选手 – 84. 柱状图中最大的矩形

题目地址

题目形容

公司

前置常识

暴力枚举 – 左右端点法（TLE）

思路

代码

暴力枚举 – 核心扩大法（TLE）

思路

代码

优化核心扩大法（Accepted）

思路

代码

枯燥栈（Accepted）

思路

代码

相干题目

第二位选手 – 85. 最大矩形

题目地址

题目形容

前置常识

公司

思路

代码

第三位选手 – 221. 最大正方形

题目地址

题目形容

前置常识

公司

思路

关键点解析

代码

如果我还想用下面的办法能够么？

总结

Just My Socks（注册教程内含优惠码）

关于算法:为何我刷了很多遇到新的题还是唯唯诺诺无法重拳出击

第一位选手 – 84. 柱状图中最大的矩形

题目地址

题目形容

公司

前置常识

暴力枚举 – 左右端点法（TLE）

思路

代码

暴力枚举 – 核心扩大法（TLE）

思路

代码

优化核心扩大法（Accepted）

思路

代码

枯燥栈（Accepted）

思路

代码

相干题目

第二位选手 – 85. 最大矩形

题目地址

题目形容

前置常识

公司

思路

代码

第三位选手 – 221. 最大正方形

题目地址

题目形容

前置常识

公司

思路

关键点解析

代码

如果我还想用下面的办法能够么？

总结

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）