Leetcode 84.柱状图中最大的矩形
原题链接 :Leetcodet原题链接
算法
(单调栈,枚举)
O
(
n
)
O(n)
O(n)
枚举每一个高度,对于每一个高度,分别找出该高度左右第一个小于该高度的索引,在找出左右第一个小于高度的索引时,我们可以维护一个单调栈来找当前高度在其中一侧的小于该高度的高度索引值
时间复杂度
对于左右侧利用单调栈来找第一个小于目前高度的高度索引值,我们只会遍历一次数组,最终找两侧的时间复杂度为 O ( 2 n ) O(2n) O(2n),最后枚举每个高度的时间复杂度也是 O ( n ) O(n) O(n),最终的时间复杂度为 O ( n ) O(n) O(n)。
C++代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s;
int n = heights.size();
vector<int> l(n), r(n);
for(int i = n - 1; i >= 0; i --)
{
int t = heights[i];
while(s.size() && heights[s.top()] >= t) s.pop();
r[i] = s.size() == 0 ? n : s.top();
s.push(i);
}
stack<int> q;
for(int i = 0; i < n; i ++)
{
int t = heights[i];
while(q.size() && heights[q.top()] >= t) q.pop();
l[i] = q.size() == 0 ? -1 : q.top();
q.push(i);
}
int res = 0;
for(int i = 0; i < n; i ++)
{
res = max(res, (r[i] - l[i] - 1) * heights[i]);
}
return res;
}
};
相关文章
- Java实现 LeetCode 826 安排工作以达到最大收益(暴力DP)
- Java实现 LeetCode 812 最大三角形面积 (暴力)
- Java实现 LeetCode 812 最大三角形面积 (暴力)
- Java实现 LeetCode 695 岛屿的最大面积(DFS)
- Java实现 LeetCode 662 二叉树最大宽度(递归)
- Java实现 LeetCode 554 砖墙(缝隙可以放在数组?)
- Java实现 LeetCode 241 为运算表达式设计优先级
- Java实现 LeetCode 164 最大间距
- Java实现 LeetCode 124 二叉树中的最大路径和
- Java实现 LeetCode 84 柱状图中最大得矩形
- Java实现 LeetCode 53 最大子序和
- 【队列&栈】LeetCode 84. 柱状图中最大的矩形【困难】
- LeetCode(84): 柱状图中最大的矩形
- 【队列&栈】LeetCode 84. 柱状图中最大的矩形【困难】
- LeetCode(94):二叉树的中序遍历
- LeetCode(85):最大矩形
- leetcode 1438. 绝对差不超过限制的最长连续子数组----双指针篇3,滑动窗口篇2
- 【leetcode】柱状图中最大的矩形(第二遍)
- 【LeetCode 简单 栈 python3】232. 用栈实现队列
- Leetcode 1399. 统计最大组的数目
- Leetcode 1323. 6 和 9 组成的最大数字
- python3的leetcode题,两个数求和等于目标值,返回这两个数的索引组成的列表(三种方法)
- LeetCode:Length of Last Word
- 【Leetcode刷题Python】104. 二叉树的最大深度
- 【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列