You are viewing a single comment's thread. Return to all comments →
static long largestRectangle(int[] h) { Stack<int[]> s = new Stack<>(); // Create stack of span = [x0, x1] int n = h.length; h = Arrays.copyOf(h, n+1); // Append a sentinel to array h int x1; int maximum = 0; for(int x0 = 0; x0 <= n; x0++) { for(x1 = x0; !s.isEmpty() && h[s.peek()[0]] >= h[x0]; ) { int[] x = s.pop(); x1 = x[1]; maximum = Math.max(maximum, h[x[0]] * (x0 - x1)); } s.push(new int[]{x0, x1}); } return maximum; }
Seems like cookies are disabled on this browser, please enable them to open this website
Largest Rectangle
You are viewing a single comment's thread. Return to all comments →
Java 8 Solution in O(n)