class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
#O(n) solution
#for each rectangle, calculate the max area formed with its height h(with h being the smallest rectangle)
#then get the max of all the results
#get the index of the first smaller rectangle to its left: left_index
#and the index of the first smaller rectangle to its right: right_index
#use mono increasing stack
if not heights: return 0
l=len(heights)
if l==1: return heights[0]
#store the index of the rectangles
#stack is mono increasing, therefore we can easily locate the most adjacent index
stack=[-1,0]
res=0
for i in range(1,l):
while len(stack)>1 and heights[i]<heights[stack[-1]]:
res=max(res,heights[stack.pop()]*(i-stack[-1]-1))
stack.append(i)
while len(stack)>1:
res=max(res,heights[stack.pop()]*(l-stack[-1]-1))
return res
84. Largest Rectangle in Histogram
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來摆出，“玉大人朗徊，你說我怎么就攤上這事≠寺” “怎么了爷恳？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長象踊。 經(jīng)常有香客問我温亲，道長棚壁，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任栈虚，我火速辦了婚禮袖外，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘魂务。我一直安慰自己曼验，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布粘姜。 她就那樣靜靜地躺著鬓照，像睡著了一般。 火紅的嫁衣襯著肌膚如雪相艇。 梳的紋絲不亂的頭發(fā)上颖杏，一...
- 文/蒼蘭香墨 我猛地睜開眼活喊，長吁一口氣：“原來是場噩夢啊……” “哼丐膝！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起钾菊，我...
- 正文 年R本政府宣布，位于F島的核電站，受9級特大地震影響奋隶，放射性物質(zhì)發(fā)生泄漏沛慢。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一达布、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧逾冬，春花似錦黍聂、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至嘀趟，卻和暖如春脐区，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背她按。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 首先，可以使用暴力破解法衰琐，以每一個數(shù)字作為高度也糊，隨后遍歷找出長度，最后進(jìn)行大小的匹配即可羡宙，但是由于是O(n^2)復(fù)...
- 題目： https://leetcode.com/problems/largest-rectangle-in-hi...
- 第一版：超時,雙層循環(huán)狸剃。 看了看tag，用棧的話辛辨，加以優(yōu)化捕捂。Largest Rectangle in Histog...
- Given n non-negative integers representing the histogram'...
- Given n non-negative integers representing the histogram'...
