Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Example:
Input: [2,1,5,6,2,3]
Output: 10
classSolution {publicintlargestRectangleArea(int[] h) {int n =h.length;Stack<Integer> st =newStack<>();int[] left =newint[n];int[] right =newint[n];// finding closest smaller element on leftfor (int i =0; i < n; i++) {while (st.size() !=0&& h[st.peek()] >= h[i]) {st.pop(); }if (st.size() ==0) left[i] =-1;else left[i] =st.peek();st.push(i); }st.clear();// finding closest smaller element on rightfor (int i = n -1; i >=0; i--) {while (st.size() !=0&& h[st.peek()] >= h[i]) {st.pop(); }if (st.size() ==0) right[i] = n;else right[i] =st.peek();st.push(i); }int max =0;for (int i =0; i < n; i++) { max =Math.max(max, h[i] * (right[i] - left[i] -1)); }return max; }}