leetcode刷题记录（八十六）——84. 柱状图中最大的矩形

（一）问题描述

84. 柱状图中最大的矩形 - 力扣（LeetCode）84. 柱状图中最大的矩形 - 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。 示例 1:[https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg]输入：heights = [2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为 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 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

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

提示：

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

（二）解决思路

        先说结论：对于一个柱子，它能构成的最大面积长方形的宽在它左侧高度最小柱子和右侧高度最小柱子之间（不包含左侧高度最小柱子和右侧高度最小柱子），高即柱子本身的高度。

        这里采用单调栈来计算各个柱子的左边界和右边界数组。以求左边界数组为例，当栈顶元素大于当前元素时就将栈顶元素弹出，并将当前柱子的位置加入栈中。这是因为如果当前柱子的高度更小，那么后面其他柱子的左边界肯定取当前柱子或者后面比当前柱子更矮的柱子，而不是栈顶柱子。

        我一开始想到了42. 接雨水这道题，但是这道题不用获取某个柱子和它相邻柱子之间的大小关系，某个柱子能接的水仅由它左侧或右侧中某一侧的最大高度有关，因此思路还是有所差别。

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;}
}