Largest Rectangle in Histogram

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.
For example,
Given heights = [2,1,5,6,2,3],
return 10.
Solution:
1. public class Solution {
2. public int largestRectangleArea(int[] h) {
3. int n = h.length, i = 0, max = 0;
4. 5. Stack s = new Stack<>();
6. 7. while (i < n) {
8. while (!s.isEmpty() && h[i] < h[s.peek()]) {
9. max = Math.max(max, h[s.pop()] * (i - (s.isEmpty() ? 0 : s.peek() + 1)));
10. }
11. s.push(i++);
12. }
13. 14. while (!s.isEmpty()) {
15. max = Math.max(max, h[s.pop()] * (n - (s.isEmpty() ? 0 : s.peek() + 1)));
16. }
17. 18. return max;
19. }
20. }