Leetcode_84 Largest Rectangle in Histogram
今天看了看Leetcode_84题,难度是hard,趁着空闲,简单地写一写吧。
原题链接:https://leetcode.com/problems/largest-rectangle-in-histogram/?tab=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.
For example,
Given heights = [2,1,5,6,2,3]
,
return 10
.
这道题开始我没有想出比较好的解法,因此参考了网上的解法,网上利用堆栈的方式解决了这道题,仔细想想本解法还是很有道理的。利用堆栈来实现类似的升序排列,时间复杂度为o(n^2)。
程序如下图所示:
最终的运行时间截图: