# Java 7ms solution beats 100% using Largest Rectangle in Histogram solved by stack simulation

• The idea is to use 【Leetcode#84】(see below comments).

As for 【LC84】, there are many fast O(n)/O(n)-time/space methods such as using a stack. Mine is to use an array nLeftGeq[] to simulate the stack so that it is faster than the default implement of stack.
Indeed, nLeftGeq[i] = the number of elements to the left of [i] having value greater than or equal to a[i] (including a[i] itself).

Since for j < i, with a[j]>a[i], we can compute the largest rectangle area with base a[j] then we throw away [j] or pop() it from the stack.

Therefore, nLeftGeq[i] is also = the index difference between [i] and the next index on the top of the stack. And thus such as peek(), pop() methods can be implemented by manipulating the array nLeftGeq[].

This sub-algorithm for 【LC84】is not the fastest one unfortunately, but still beats 95.45%.

``````public int maximalRectangle(char[][] matrix) {
/**
* idea: using [LC84 Largest Rectangle in Histogram]. For each row
* of the matrix, construct the histogram based on the current row
* and the previous histogram (up to the previous row), then compute
* the largest rectangle area using LC84.
*/
int m = matrix.length, n;
if (m == 0 || (n = matrix[0].length) == 0)
return 0;

int i, j, res = 0;
int[] heights = new int[n];
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (matrix[i][j] == '0')
heights[j] = 0;
else
heights[j] += 1;
}
res = Math.max(res, largestRectangleArea(heights));
}

return res;
}

public int largestRectangleArea(int[] heights) {
/**
* idea: scan and store if a[i-1]<=a[i] (increasing), then as long
* as a[i]<a[i-1], then we can compute the largest rectangle area
* with base a[j], for j<=i-1, and a[j]>a[i], which is a[j]*(i-j).
* And meanwhile, all these bars (a[j]'s) are already done, and thus
* are throwable (using pop() with a stack).
*
* We can use an array nLeftGeq[] of size n to simulate a stack.
* nLeftGeq[i] = the number of elements to the left of [i] having
* value greater than or equal to a[i] (including a[i] itself). It
* is also the index difference between [i] and the next index on
* the top of the stack.
*/
int n = heights.length;
if (n == 0)
return 0;

int[] nLeftGeq = new int[n]; // the number of elements to the left
// of [i] with value >= heights[i]
nLeftGeq[0] = 1;

// preIdx=the index of stack.peek(), res=max area so far
int preIdx = 0, res = 0;

for (int i = 1; i < n; i++) {
nLeftGeq[i] = 1;

// notice that preIdx = i - 1 = peek()
while (preIdx >= 0 && heights[i] < heights[preIdx]) {
res = Math.max(res, heights[preIdx] * (nLeftGeq[preIdx] + i - preIdx - 1));
nLeftGeq[i] += nLeftGeq[preIdx]; // pop()

preIdx = preIdx - nLeftGeq[preIdx]; // peek() current top
}

if (preIdx >= 0 && heights[i] == heights[preIdx])
nLeftGeq[i] += nLeftGeq[preIdx]; // pop()
// otherwise nothing to do

preIdx = i;
}

// compute the rest largest rectangle areas with (indices of) bases
// on stack
while (preIdx >= 0 && 0 < heights[preIdx]) {
res = Math.max(res, heights[preIdx] * (nLeftGeq[preIdx] + n - preIdx - 1));
preIdx = preIdx - nLeftGeq[preIdx]; // peek() current top
}

return res;
}``````

• OMG, both are excellent solutions for problems 84 and 85.

• if (preIdx >= 0 && heights[i] == heights[preIdx])
nLeftGeq[i] += nLeftGeq[preIdx]; // pop()

I remove them and still got AC. Maybe we don't need them.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.