[leetcode] 84. Largest Rectangle in Histogram

[leetcode] 84. Largest Rectangle in Histogram

Description

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.

Example:

Input: [2,1,5,6,2,3]Output: 10

分析

题目的意思是：给你一个柱形图数组，求能够围成的最大的矩形。

栈存储的是下标，维护的是递增序列，如果不递增，则出栈计算长度。用栈计算每一块板能延伸到的左右边界 ，对每一块板；栈顶矮，这一块左边界确定，入栈；堆栈顶高，栈顶右边界确定，出栈，计算面积入栈时左边界确定，出栈时右边界确定，栈里元素是递增的。时间复杂度 O(n)，leetcode hard难度。

代码

class Solution {public: int largestRectangleArea(vector& heights) { heights.push_back(-1); stack s; int index=0; int sum=0; while(index

参考文献

​​[编程题]largest-rectangle-in-histogram​​​​leetcode之Largest Rectangle in Histogram​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。