84.柱狀圖中最大的矩形

力扣題目鏈接

給定 n 個(gè)非負(fù)整數(shù)，用來(lái)表示柱狀圖中各個(gè)柱子的高度。每個(gè)柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來(lái)的矩形的最大面積。

• 1 <= heights.length <=10^5

• 0 <= heights[i] <= 10^4

• 暴力解法

class Solution {public int largestRectangleArea(int[] heights) {int res=0;for(int i=0;i<heights.length;i++){int left=i;int right=i;for(;left>=0;left--){if(heights[left]<heights[i]) break;}for(;right<heights.length;right++){if(heights[right]<heights[i]) break;}int w=right-left-1;int h=heights[i];res=Math.max(res,w*h);}return res;}
}

• 單調(diào)棧解法

求左右兩邊小的, 用單調(diào)遞減棧

主要就是分析清楚如下三種情況：

• 情況一：當(dāng)前遍歷的元素heights[i]大于棧頂元素heights[st.top()]的情況
• 情況二：當(dāng)前遍歷的元素heights[i]等于棧頂元素heights[st.top()]的情況
• 情況三：當(dāng)前遍歷的元素heights[i]小于棧頂元素heights[st.top()]的情況

頭尾要加0 ,如果數(shù)組本身就是升序的，例如[2,4,6,8]，那么入棧之后 都是單調(diào)遞減，一直都沒(méi)有走 情況三 計(jì)算結(jié)果的哪一步，所以最后輸出的就是0了,那么結(jié)尾加一個(gè)0，就會(huì)讓棧里的所有元素，走到情況三的邏輯。如圖：

那么結(jié)尾加一個(gè)0，就會(huì)讓棧里的所有元素，走到情況三的邏輯。

開頭為什么要加元素0？

如果數(shù)組本身是降序的，例如 [8,6,4,2]，在 8 入棧后，6 開始與8 進(jìn)行比較，此時(shí)我們得到 mid（8），rigt（6），但是得不到 left。

（mid、left，right 都是對(duì)應(yīng)版本一里的邏輯）

因?yàn)?將 8 彈出之后，棧里沒(méi)有元素了，那么為了避免空棧取值，直接跳過(guò)了計(jì)算結(jié)果的邏輯。

之后又將6 加入棧（此時(shí)8已經(jīng)彈出了），然后 就是 4 與 ?？谠?8 進(jìn)行比較，周而復(fù)始，那么計(jì)算的最后結(jié)果resutl就是0。 如圖所示：

所以我們需要在 height數(shù)組前后各加一個(gè)元素0。

整體代碼如下:

class Solution {public int largestRectangleArea(int[] heights) {int res=0;int[] newheights=new int[heights.length+2];System.arraycopy(heights,0,newheights,1,heights.length);newheights[0]=0;newheights[heights.length+1]=0;Deque<Integer> stack=new LinkedList<>();stack.push(0);for(int i=1;i<newheights.length;i++){while(!stack.isEmpty()&&newheights[i]<newheights[stack.peek()]){int mid=stack.peek();stack.pop();int w=i-stack.peek()-1;int h=newheights[mid];res=Math.max(res,w*h);}stack.push(i);}return res;}
}