Search for a command to run...
Try your own input
Change the array and replay the algorithm from step one.
The boundary idea
For each bar, the largest rectangle using that bar as its height spans from just after the previous smaller bar to just before the next smaller bar. Width = nse[i] − pse[i] − 1.
Precompute NSE & PSE
1function findNSE(arr) {2 const n = arr.length, ans = new Array(n), st = [];3 for (let i = n - 1; i >= 0; i--) {4 while (st.length && arr[st[st.length - 1]] >= arr[i]) st.pop();5 ans[i] = st.length ? st[st.length - 1] : n;6 st.push(i);7 }8 return ans;9}10 11function findPSE(arr) {12 const n = arr.length, ans = new Array(n), st = [];13 for (let i = 0; i < n; i++) {14 while (st.length && arr[st[st.length - 1]] >= arr[i]) st.pop();15 ans[i] = st.length ? st[st.length - 1] : -1;16 st.push(i);17 }18 return ans;19}20 21function largestRectangleArea(heights) {22 const nse = findNSE(heights), pse = findPSE(heights);//n: 6largestArea: 023 let largestArea = 0;24 for (let i = 0; i < heights.length; i++) {25 const area = heights[i] * (nse[i] - pse[i] - 1);26 largestArea = Math.max(largestArea, area);27 }28 return largestArea;29}