題目描述:
給定n個非負整數height[n],分別代表直方圖條的高,每個條的寬設為1,求直方圖中面積最大的矩形的面積
題目來源:
http://oj.leetcode.com/problems/largest-rectangle-in-histogram/
題目分析:
維護一個棧,保存直方圖條的下標,當當前棧為空或者棧頂的下標所表示的元素不大于當前元素時,入棧,否則出棧,直到可以把當前元素壓入棧中
(1)對于當前棧,假設序列為a1, a2,...ai, ai+1, a...棧頂,那么處于ai和ai+1之間的元素一定大于ai+1,如果他們中的最小元素小于等于ai+1,那么它一定在棧中,故棧中處于ai和ai+1之間的元素一定大于ai+1
(2)計算矩形的面積,可以考慮以待計算的元素為中心,向右擴展最遠,并且向左擴展最遠
(3)出棧時,計算以剛出棧的元素為高的最大矩形,它向左擴展最遠到棧中的下一個元素,向右擴展最遠到當前元素(因為當前元素比他小)
- 時間復雜度: O(n)
- 示例代碼:
int maxArea(vector< int > vi) { stack < int > st; int maxArea = 0 , i = 0 ; while (i <= n) { if (st.empty() || vi[st.top()] <= vi[i]) { st.push(i ++ ); } else { int tmp = st.top(); st.pop(); maxArea = max(maxArea, vi[tmp] * (st.empty() ? i : i - st.top() - 1 )); } } return maxArea; }
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
