【hot100-java】【柱状图中最大的矩形】

R9-栈篇

面积最大矩形的高度一定是 heights 中的元素

简单解释，就是说，最大高度必然是heights中的一个元素，我们假设是h，然后我们基于h，左右拓展，尽量拓展到h越来越高（符合单调栈），这样能保证left~right之间的最高高度都是h.

Deque<Integer>st=new ArrayDeque<>();
//整形双端队列

peek()取出队列头部元素

class Solution {public int largestRectangleArea(int[] heights) {int n=heights.length;int [] left=new int[n];Deque<Integer>st=new ArrayDeque<>();for (int i=0;i<n;i++){int x=heights[i];while(!st.isEmpty()&&x<=heights[st.peek()]){st.pop();}left[i]=st.isEmpty()?-1:st.peek();st.push(i);}//开始处理右边int [] right=new int[n];st.clear();for (int i=n-1;i>=0;i--){int x=heights[i];while(!st.isEmpty()&&x<=heights[st.peek()]){st.pop();}right[i]=st.isEmpty()?n:st.peek();st.push(i);}    //返回结果处理int ret=0;for (int i=0;i<n;i++){ret=Math.max(ret,heights[i]*(right[i]-left[i]-1));}      return ret;}
}