image.png
import java.util.Stack;
class Solution {
public int largestRectangleArea(int[] height) {
Stack<Integer>st=new Stack<Integer>();
int res = 0;
int[]a = new int[height.length+1];
for(int i=0;i<height.length;i++)a[i]=height[i];
a[height.length]=0;
for(int i=0; i<a.length; i++) {
while(!st.isEmpty() && a[st.peek()]>=a[i]) {
int idx = st.pop();
int width = i-(st.isEmpty()?-1:st.peek())-1;
res = Math.max(res, a[idx]*width);
}
st.add(i);
}
return res;
}
public static void main(String[] args) {
Solution s=new Solution();
System.out.println(s.largestRectangleArea(new int[]{2,1,5,6,2,3}));
System.out.println(s.largestRectangleArea(new int[]{1}));
}
}
