为何我刷了很多题，遇到新的题还是气宇轩昂，无奈重拳出击？为何一看就会一些就废？这其中又暗藏着怎么的机密？到底是道德的沦丧还是兽性的扭曲？欢送收看本期的 走出迷信 特地栏目。
明天给大家带来了三位重量级选手，一位体重 98 公斤，一位体重 100 公斤，还有一位体重 98 斤，明天 lucifer 就带大家用同样的招式 KO 他们三位。
第一位选手 - 84. 柱状图中最大的矩形
题目地址
https://leetcode-cn.com/probl...
题目形容
给定 n 个非负整数，用来示意柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，可能勾画进去的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中暗影局部为所能勾画出的最大矩形面积，其面积为 10 个单位。
示例：输出：[2,1,5,6,2,3]输入：10公司
- 阿里
- 腾讯
- 百度
- 字节
前置常识
- 枯燥栈
暴力枚举 - 左右端点法（TLE）
思路
咱们暴力尝试所有可能的矩形。因为矩阵是二维图形， 我咱们能够应用左右两个端点来惟一确认一个矩阵。因而咱们应用双层循环枚举所有的可能性即可。 而矩形的面积等于（右端点坐标 - 左端点坐标 + 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)$
暴力枚举 - 核心扩大法（TLE）
思路
咱们依然暴力尝试所有可能的矩形。只不过咱们这一次从核心向两边进行扩大。对于每一个 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)$
优化核心扩大法（Accepted）
思路
实际上咱们内层循环没必要一步一步挪动，咱们能够间接将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)$
枯燥栈（Accepted）
思路
实际上，读完第二种办法的时候，你应该留神到了。咱们的外围是求右边第一个比 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 ansCPP 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
第二位选手 - 85. 最大矩形
题目地址
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)$
第三位选手 - 221. 最大正方形
题目地址
https://leetcode-cn.com/probl...
题目形容
在一个由 0 和 1 组成的二维矩阵内，找到只蕴含 1 的最大正方形，并返回其面积。示例:输出:1 0 1 0 01 0 1 1 11 1 1 1 11 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 ** 2JavaScript 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 题目不成问题。