题目列表
84. 柱状图中最大的矩形(单调栈找左右两边第一个更低的位置)
https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
提示:1 <= heights.length <=10^5
0 <= heights[i] <= 10^4
以 heights[i] 为高度的矩形,它的宽是* (r[i] - l[i] - 1);
其中 r[i] 和 l[i] 为左右两边第一个更低的位置。
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
// 记录左右第一个比它小的下标
int[] l = new int[n], r = new int[n];
Arrays.fill(l, -1); // 左边第一个大于heights[i]
Arrays.fill(r, n); // 右边第一个小于等于heights[i]
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && heights[i] <= heights[stk.peek()]) {
r[stk.pop()] = i;
}
if (!stk.isEmpty()) l[i] = stk.peek();
stk.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int s = heights[i] * (r[i] - l[i] - 1);
if (s > ans) ans = s;
}
return ans;
}
}
从具体结果来看,r[i] 表示的是小于等于的而不是小于的,这看起来会出错但其实并不会。
原因在于,如果h[i]和h[j]是相同的高度,那么r[i]=j这是错误的,但是r[j]可以得出正确的答案。
具体看下面的例子:
85. 最大矩形⭐⭐⭐⭐⭐
https://leetcode.cn/problems/maximal-rectangle/description/
提示:rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'
解法1——使用柱状图的优化暴力方法
https://leetcode.cn/problems/maximal-rectangle/solutions/535672/zui-da-ju-xing-by-leetcode-solution-bjlu/
总结一下思路:
- 预处理出 left[i][j],是每个点作为右下角时,它的左边包括多少连续的1。
- 枚举每个点作为右下角,计算其最大面积。随着高度的变大,宽度会随之减小。
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
// 构造 left 数组
int[][] left = new int[m][n];
for (int i = 0; i < m; ++i) {
if (matrix[i][0] == '1') left[i][0] = 1;
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == '1') {
left[i][j] = left[i][j - 1] + 1;
}
}
}
int ans = 0;
// 枚举每个点(i,j)作为右下角
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int width = left[i][j], area = width * 1;
// 尝试扩展高度
for (int k = i - 1; k >= 0; --k) {
width = Math.min(width, left[k][j]);
area = Math.max(area, width * (i - k + 1));
}
ans = Math.max(ans, area);
}
}
return ans;
}
}
解法2——单调栈 :归因到 84. 柱状图中最大的矩形 🐂
解法1 需要枚举每个点,对于每个点又有 m 的复杂度,所以时间复杂度是 O ( m 2 ∗ n ) O(m^2*n) O(m2∗n)
可以优化成求解每一行 m,对于每一行,相当于 84. 柱状图中最大的矩形 的时间复杂度,总的复杂度是 O ( m ∗ n ) O(m*n) O(m∗n)。
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[] h = new int[n];
int[] l = new int[n], r = new int[n];
int ans = 0;
for (int i = 0; i < m; ++i) {
// 处理以第 i 行为底的矩形
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') h[j]++;
else h[j] = 0;
}
// 利用单调栈求解
Deque<Integer> stk = new ArrayDeque<>();
Arrays.fill(l, -1);
Arrays.fill(r, n);
for (int j = 0; j < n; ++j) {
while (!stk.isEmpty() && h[j] < h[stk.peek()]) {
r[stk.pop()] = j;
}
if (!stk.isEmpty()) l[j] = stk.peek();
stk.push(j);
}
int area = 0;
for (int j = 0; j < n; ++j) {
area = Math.max(area, h[j] * (r[j] - l[j] - 1));
}
if (area > ans) ans = area;
}
return ans;
}
}
1504. 统计全 1 子矩形⭐
https://leetcode.cn/problems/count-submatrices-with-all-ones/description/
提示:1 <= m, n <= 150
mat[i][j] 仅包含 0 或 1
解法1——枚举 O ( m 2 ∗ n ) O(m^2*n) O(m2∗n)
class Solution {
public int numSubmat(int[][] mat) {
int m = mat.length, n = mat[0].length, ans = 0;
int[][] left = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (mat[i - 1][j - 1] == 1) {
left[i][j] = left[i][j - 1] + 1;
}
int w = left[i][j];
for (int k = i; k >= 1 && w > 0; --k) {
w = Math.min(w, left[k][j]);
ans += w; // 每个高度有w个宽度可选
}
}
}
return ans;
}
}
解法2——单调栈优化⭐⭐⭐⭐⭐(比较难理解,细细品味)
配合官解食用,https://leetcode.cn/problems/count-submatrices-with-all-ones/solutions/336410/tong-ji-quan-1-zi-ju-xing-by-leetcode-solution/
为了复用上面的结果,需要用单调栈维护一个单调非递减的序列,只有这样才能满足:该层的 sum 是上层的 sum + 该层的 w。
否则,应该去除上层的额外宽度 w,同时保留其去除额外宽度之后的高度 h,加入当前层,再送入栈中。文章来源:https://www.toymoban.com/news/detail-768922.html
class Solution {
public int numSubmat(int[][] mat) {
int m = mat.length, n = mat[0].length, ans = 0;
int[][] left = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (mat[i - 1][j - 1] == 1) {
left[i][j] = left[i][j - 1] + 1;
}
}
}
// 枚举每一列
for (int j = 0; j < n; ++j) {
Deque<int[]> stk = new ArrayDeque<>(); // 记录元素是[left[][], height]
// 从上到下枚举每一行
for (int i = 0, sum = 0; i < m; ++i) {
int height = 1; // 初始高度为1
// 维护宽度单调递增的单调队列
while (!stk.isEmpty() && stk.peek()[0] > left[i + 1][j + 1]) {
// 去除无效的额外宽度
sum -= stk.peek()[1] * (stk.peek()[0] - left[i + 1][j + 1]);
height += stk.pop()[1]; // 继承移除的高度
}
sum += left[i + 1][j + 1]; // 矩形数量加上当前层的宽度
ans += sum;
stk.push(new int[]{left[i + 1][j + 1], height});
}
}
return ans;
}
}
相关链接
【算法】单调栈题单(矩阵系列、字典序最小、贡献法)文章来源地址https://www.toymoban.com/news/detail-768922.html
到了这里,关于【算法】单调栈题单——矩阵系列⭐的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!