Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]
.
The largest rectangle is shown in the shaded area, which has area = 10
unit.
For example,
Given height = [2,1,5,6,2,3]
,
return 10
.
方法1:
这个方法会TLE!
O(n log n),而且最快情况下,变成O(n^2).
之所以把这个写下来,是因为我蠢!
对于任意i~j, area = (j-i+1) * min(a[i]...a[j]);
因此在i~j内,如果要有更大的area,则必定需要去掉a[k] = min(a[i]...a[j]).
去掉a[k]后,则分成2段:i~k-1, k+1~j。则变成2个子问题。
class Solution { public: int largestRectangleArea(vector<int> &height) { if (height.size() == 0) return 0; return maxarea(&height[0], 0, height.size() - 1); } int maxarea(int* a, int start, int end) { if (start > end) return 0; if (start == end) return a[start]; int minidx = start, minh = a[minidx]; for (int i = start+1; i <= end; i++) { if (a[i] < minh) { minh = a[i]; minidx = i; } } int tmp = (end - start + 1) * minh; int left = maxarea(a, start, minidx - 1); int right = maxarea(a, minidx + 1, end); int res = max(tmp, left); res = max(res, right); return res; } };
方法2:
对于每一块板,找到left,right两边。离它最远的那个比不它矮的板。也就是等价于找到离他最近的那个比它矮的板a[k]。那么a[k-1]那块就是最远的不比他短的板。因为找到离他最近的比他矮的板,这是一个单调序列问题,可以O(N)处理。
所以分别O(N)处理left,right。
然后再O(N)扫一遍,对于每快以a[i]为最矮的矩形面积为maxarea[i] = (right-left) * a[i];
class Solution { public: int largestRectangleArea(vector<int> &height) { int len = height.size(); if (len == 0) return 0; vector<int> left(len, -1); vector<int> right(len, -1); left[0] = -1; stack<int> s; int *a = &height[0]; for (int i = 0; i < len; i++) { while (!s.empty()) { if (a[s.top()] >= a[i]) s.pop(); else break; } if (!s.empty()) left[i] = s.top(); else left[i] = -1; s.push(i); } while(!s.empty()) s.pop(); for (int i = len - 1; i >= 0; i--) { while (!s.empty()) { if (a[s.top()] >= a[i]) s.pop(); else break; } if (!s.empty()) right[i] = s.top(); else right[i] = len; s.push(i); } int res = -1; for (int i = 0; i < len; i++) { res = max(res, height[i]*(right[i] - left[i] - 1)); } return res; } };
Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { auto &a = matrix; int n = a.size(); if (n == 0) return 0; int m = a[0].size(); vector<int> b(m, 0); int res = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == '0') b[j] = 0; else b[j] += 1; } vector<int> left(m, 0); stack<int> s; for (int j = 0; j < m; j++) { while (!s.empty() && b[s.top()] >= b[j]) s.pop(); if (s.empty()) left[j] = -1; else left[j] = s.top(); s.push(j); } while (!s.empty()) s.pop(); vector<int> right(m, 0); for (int j = m - 1; j >= 0; j--) { while (!s.empty() && b[s.top()] >= b[j]) s.pop(); if (s.empty()) right[j] = m; else right[j] = s.top(); s.push(j); } for (int j = 0; j < m; j++) { if (a[i][j] == '0') continue; int t = b[j] * (right[j] - 1 - left[j]); if (t > res) res = t; } } return res; } };
相关推荐
在LeetCode这个著名的在线编程挑战平台上,有一道题目名为“Largest Rectangle in Histogram”(直译为“柱状图中的最大矩形”),这是一道与数据结构和算法密切相关的题目,旨在考察程序员对栈、动态规划以及几何...
leetcode中文版 「LeetCode-习题集」使用说明 | 中文说明 简介 「LeetCode-习题集」是由热爱算法的 LeetCoders 上传的代码集,我们的目标是贡献所有题解!如果您想成为代码贡献者,体会 GitHub 协同合作的乐趣,请...
这是来自LeetCode的已解决任务的存储库使用Java语言解决任务 CoinChange.java - //leetcode.com/problems/coin-change/ ProductOfArrayExceptSelf.java - //leetcode.com/problems/product-of-array-except-self/ ...
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
leetcode leetcode Java 中的 Leetcode 解决方案 基础 (简单的) (简单的) (简单的) (中等的) (简单的) (难的) (中等的) (中等的) (简单的) (简单的) 二分查找 桶 提高 【两个排序数组的4中位数...
python python_leetcode题解之084_Largest_Rectangle_in_Histogram
c c语言_leetcode题解之0084_largest_rectangle_in_histogram.zip
javascript js_leetcode题解之84-largest-rectangle-in-histogram.js
leetcode/lintcode 的问题以及我的解决方案。 类别 专业算法 名称 专业化 例子 Boyer-Moore 投票算法 使用线性时间和恒定空间查找元素序列的大部分。 加泰罗尼亚号码 组合数学中的计数问题 需要更多练习 动态规划 ...
相关题目如《数组中第k个最大元素》(https://leetcode-cn.com/problems/kth-largest-element-in-an-array/)。 2. 排序问题:合并两个已排序的数组、将数字组成最大数等。例如《合并两个有序数组》...
Leetcode/剑指offer/一些算法题目集锦 题目 所使用语言 所属网站 文件位置 二维数组查找 C++ 牛客网 二叉树的坡度 C++ Leetcode 替换空格 C++ 牛客网 二进制中1的个数 C++ 牛客网 调整数组顺序 C++ 牛客网 合并两个...
leetcode题库 leetcode 生成文件工具 Usage: python tool.py -p [name] [options] Options: -h, --h 查看帮助 -p name leetcode 题目编号,必须 -a 题目类型为算法 -d 题目类型为数据库 -s 题目类型为Shell -c 编程...
http://blog.csdn.net/two_water/article/details/53004027 LeetCode_直方图最大面积(Largest Rectangle in Histogram)
vscode提交leetcode Leetcode刷题存档 准备 vscode 安装 leetcode 插件 添加leetcode到bin ln -s ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/...
LeetCode 是一个在线编程平台,专注于提供算法题目供程序员练习,提升编程技能,特别是解决算法问题的能力。在LeetCode上,你可以找到各种难度级别的编程挑战,涵盖了数据结构、算法、设计模式等多个领域,有助于...
颜色分类leetcode 实时人脸检测和情感/性别分类使用 fer2013/IMDB 颜色分类leetcode 实时人脸检测和情感/性别分类使用 fer2013/IMDB 颜色分类leetcode 实时人脸检测和情感/性别分类使用 fer2013/IMDB 颜色分类...
leetcode 638 Python :grinning_face_with_big_eyes: 让我们一起享受 LeetCode 的乐趣吧! 我已经解决了这些问题。 ID 标题 Python C++ 去 1 二 3 4 5 6 一切 7 一切 8 一切 一切 9 一切 10 一切 一切 十一 一切 13 ...
python python_leetcode题解之085_Maximal_Rectangle
leetcode 答案 leetcode题目列表 题目在注释里说明 预定义了go的模板 注释格式如下 /* 1:两数之和 leetcodeID : 1 leetcode地址 : https://leetcode-cn.com/problems/two-sum/ 难度 : 简单 给定一个整数数组 nums 和...
leetcode寻找最近的 其他 ...https://github.com/yangyu2010/leetcode/blob/master/leetcode/1两数之和.py 整数反转 https://github.com/yangyu2010/leetcode/blob/master/leetcode/7整数反转.py 加一 ...