【算法】单调栈题单——矩阵系列⭐

这篇具有很好参考价值的文章主要介绍了【算法】单调栈题单——矩阵系列⭐。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目列表

84. 柱状图中最大的矩形(单调栈找左右两边第一个更低的位置)

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

【算法】单调栈题单——矩阵系列⭐,算法刷题记录,算法,矩阵,单调栈,矩形,力扣,leetcode,栈

提示:
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]可以得出正确的答案。
具体看下面的例子:
【算法】单调栈题单——矩阵系列⭐,算法刷题记录,算法,矩阵,单调栈,矩形,力扣,leetcode,栈

85. 最大矩形⭐⭐⭐⭐⭐

https://leetcode.cn/problems/maximal-rectangle/description/

【算法】单调栈题单——矩阵系列⭐,算法刷题记录,算法,矩阵,单调栈,矩形,力扣,leetcode,栈

提示:
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/

【算法】单调栈题单——矩阵系列⭐,算法刷题记录,算法,矩阵,单调栈,矩形,力扣,leetcode,栈
【算法】单调栈题单——矩阵系列⭐,算法刷题记录,算法,矩阵,单调栈,矩形,力扣,leetcode,栈


总结一下思路:

  1. 预处理出 left[i][j],是每个点作为右下角时,它的左边包括多少连续的1。
  2. 枚举每个点作为右下角,计算其最大面积。随着高度的变大,宽度会随之减小。
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(m2n)

可以优化成求解每一行 m,对于每一行,相当于 84. 柱状图中最大的矩形 的时间复杂度,总的复杂度是 O ( m ∗ n ) O(m*n) O(mn)

【算法】单调栈题单——矩阵系列⭐,算法刷题记录,算法,矩阵,单调栈,矩形,力扣,leetcode,栈

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/

【算法】单调栈题单——矩阵系列⭐,算法刷题记录,算法,矩阵,单调栈,矩形,力扣,leetcode,栈

提示:
1 <= m, n <= 150
mat[i][j] 仅包含 0 或 1

解法1——枚举 O ( m 2 ∗ n ) O(m^2*n) O(m2n)

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/

【算法】单调栈题单——矩阵系列⭐,算法刷题记录,算法,矩阵,单调栈,矩形,力扣,leetcode,栈
【算法】单调栈题单——矩阵系列⭐,算法刷题记录,算法,矩阵,单调栈,矩形,力扣,leetcode,栈

为了复用上面的结果,需要用单调栈维护一个单调非递减的序列,只有这样才能满足:该层的 sum 是上层的 sum + 该层的 w
否则,应该去除上层的额外宽度 w,同时保留其去除额外宽度之后的高度 h,加入当前层,再送入栈中。

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 面试算法40:矩阵中的最大矩形

    请在一个由0、1组成的矩阵中找出最大的只包含1的矩形并输出它的面积。例如,在图6.6的矩阵中,最大的只包含1的矩阵如阴影部分所示,它的面积是6。 直方图是由排列在同一基线上的相邻柱子组成的图形。由于题目要求矩形中只包含数字1,因此将矩阵中上下相邻的值为1的

    2024年02月06日
    浏览(53)
  • 单调栈练习(四)— 统计全 1 子矩形

    题目 同样的LeetCode原题:题目链接 给你一个 m x n 的二进制矩阵 mat ,请你返回有多少个 子矩形 的元素全部都是 1 。 单调栈 解题思路整体和上一篇文章差不多,都是用到了 压缩数组 的技巧,通过压缩数组来构建一个数组矩阵、以每一行为底, 每一列作为矩阵的高度,区别

    2024年01月24日
    浏览(44)
  • 【力扣】84. 柱状图中最大的矩形 <模拟、双指针、单调栈>

    给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。 示例 1: 输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10 示例 2: 输入: heights = [2,4] 输出: 4 提示

    2024年02月12日
    浏览(68)
  • Leetcode面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年01月16日
    浏览(72)
  • Leetcod面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年02月03日
    浏览(43)
  • LeetCode刷题系列 -- 54. 螺旋矩阵

    给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 示例 1: 输入: matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出: [1,2,3,4,8,12,11,10,9,5,6,7] 提示: m == matrix.length n == matrix[i].length 1 =

    2023年04月08日
    浏览(61)
  • 吃透单调栈(2)——解两道Hard题:接雨水、柱状图中最大的矩形问题

    这类题目的数据通常是一维数组,要寻找任一个元素的 右边或者左边 第一个 比自己 大 或者 小 的元素的位置(寻找 边界 ) ,此时我们就要想到可以用单调栈了。   这道题就是要求解每一个柱子左边第一个比它高的柱子,以及右边第一个比它高的柱子,然后这两个柱子间

    2024年02月10日
    浏览(35)
  • 算法刷题-数组-螺旋矩阵

    力扣题目链接 给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 这道题目可以说在面试中出现频率较高的题目, 本题并不涉及到什么算法,就是模拟过程,但却十分考察对代

    2024年02月08日
    浏览(55)
  • 洛谷题单 Part 6.7.1 矩阵

    应队友要求,开始学线性代数,具体路线是矩阵 → rightarrow → 高斯消元 → rightarrow → 线性基。为多项式做个准备 题面 板子,用结构体写的,感觉有点丑,一会儿看看题解有没有写得好看的 题面 搞个方阵 A 3 = [ a 3 a 2 a 1 0 0 0 0 0 0 ] , X = [ 1 1 0 0 0 1 1 0 0 ] , A_3=left [ begin{ma

    2024年02月15日
    浏览(48)
  • 算法刷题记录

    cf题目记录 773 A题 给定三个坐标 就是让你求两个y相同时x的差,这个y要是最大的y 收获:ans我本来定义的是double,因为我看题目输出是浮点数,然后wa了,发现大数相减时,会把后面的省略了,比如 然后把double改为int就行了,因为减数和被减数都是int型的 772 B A题 题意 如果两

    2024年02月15日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包