（一）問題描述

84. 柱狀圖中最大的矩形 - 力扣（LeetCode）84. 柱狀圖中最大的矩形 - 給定 n 個(gè)非負(fù)整數(shù)，用來表示柱狀圖中各個(gè)柱子的高度。每個(gè)柱子彼此相鄰，且寬度為 1 。求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。?示例 1:[https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg]輸入：heights = [2,1,5,6,2,3]輸出：10解釋：最大的矩形為圖中紅色區(qū)域，面積為 10示例 2：[https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg]輸入： heights = [2,4]輸出： 4?提示： * 1 <= heights.length <=105 * 0 <= heights[i] <= 104https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked

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

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

示例 1:

輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：最大的矩形為圖中紅色區(qū)域，面積為 10

示例 2：

輸入： heights = [2,4]
輸出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

（二）解決思路

????????先說結(jié)論：對(duì)于一個(gè)柱子，它能構(gòu)成的最大面積長(zhǎng)方形的寬在它左側(cè)高度最小柱子和右側(cè)高度最小柱子之間（不包含左側(cè)高度最小柱子和右側(cè)高度最小柱子），高即柱子本身的高度。

????????這里采用單調(diào)棧來計(jì)算各個(gè)柱子的左邊界和右邊界數(shù)組。以求左邊界數(shù)組為例，當(dāng)棧頂元素大于當(dāng)前元素時(shí)就將棧頂元素彈出，并將當(dāng)前柱子的位置加入棧中。這是因?yàn)槿绻?dāng)前柱子的高度更小，那么后面其他柱子的左邊界肯定取當(dāng)前柱子或者后面比當(dāng)前柱子更矮的柱子，而不是棧頂柱子。

????????我一開始想到了42. 接雨水這道題，但是這道題不用獲取某個(gè)柱子和它相鄰柱子之間的大小關(guān)系，某個(gè)柱子能接的水僅由它左側(cè)或右側(cè)中某一側(cè)的最大高度有關(guān)，因此思路還是有所差別。

class Solution {public int largestRectangleArea(int[] heights) {int n=heights.length;Stack<Integer> st=new Stack<>();//求左邊界int[] left=new int[n];for(int i=0;i<heights.length;i++){while(!st.isEmpty()&&heights[i]<=heights[st.peek()]){st.pop();}left[i]=(st.isEmpty()?-1:st.peek());st.push(i);}st.clear();//求右邊界int[] right=new int[n];for(int i=n-1;i>=0;i--){while(!st.isEmpty()&&heights[i]<=heights[st.peek()]){st.pop();}right[i]=(st.isEmpty())?n:st.peek();st.push(i);}int ans=0;for(int i=0;i<n;i++){ans=Math.max(ans,(right[i]-left[i]-1)*heights[i]);}return ans;}
}