博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Q85 最大矩形
阅读量:6153 次
发布时间:2019-06-21

本文共 1457 字,大约阅读时间需要 4 分钟。

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

示例:

输入:[  ["1","0","1","0","0"],  ["1","0","1","1","1"],  ["1","1","1","1","1"],  ["1","0","0","1","0"]]输出: 6
class Solution {    public int maximalRectangle(char[][] matrix) {        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)            return 0;        int[] sum = new int[matrix[0].length];        int max = 0;        for (int i = 0; i < matrix.length; i++) {            for (int j = 0; j < matrix[0].length; j++) {                sum[j] = matrix[i][j] == '0' ? 0 : sum[j] + 1;            }            int t = findMax(sum);            max = max > t ? max : t;        }        return max;    }    private int findMax(int[] nums) {        int max = 0;        Deque
stack = new LinkedList<>(); for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) { int j = stack.pop(); int left = stack.isEmpty() ? -1 : stack.peek(); int size = (i - left - 1) * nums[j]; max = max > size ? max : size; } stack.push(i); } while (!stack.isEmpty()) { int j = stack.pop(); int left = stack.isEmpty() ? -1 : stack.peek(); int size = (nums.length - left - 1) * nums[j]; max = max > size ? max : size; } return max; }}

转载于:https://www.cnblogs.com/WeichengDDD/p/10830864.html

你可能感兴趣的文章
Webpack 2 中一些常见的优化措施
查看>>
移动端响应式
查看>>
js中var、let、const的区别
查看>>
简洁优雅地实现夜间模式
查看>>
react学习总结
查看>>
在soapui上踩过的坑
查看>>
MySQL的字符集和字符编码笔记
查看>>
ntpd同步时间
查看>>
must implement java.io.Serializable hessian
查看>>
Microsoft Licenses Flash Lite for Windows Mobile Users
查看>>
HDOJ 2020 绝对值排序
查看>>
HDOJ/HDU 2560 Buildings(嗯~水题)
查看>>
Maven编译时跳过Test
查看>>
Spring Boot 整合Spring Security 和Swagger2 遇到的问题小结
查看>>
[20170628]12C ORA-54032.txt
查看>>
linux运维人员的成功面试总结案例分享
查看>>
Windows DHCP Server基于MAC地址过滤客户端请求实现IP地址的分配
查看>>
命令查询每个文件文件数
查看>>
《跟阿铭学Linux》第8章 文档的压缩与打包:课后习题与答案
查看>>
RAC表决磁盘管理和维护
查看>>