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)。

程序如下图所示:

最终的运行时间截图:

 

共有 0 条评论

Top