Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
O(n) solution in Clear category for Largest Rectangle in a Histogram by Sim0000
import assert from "assert";
function largestHistogram(values: number[]): number {
const n = values.length;
const stack: number[] = [];
const peek = () => stack[stack.length - 1];
let max_area: number = 0;
function update(i){
const p: number = stack.pop();
const width: number = stack.length == 0 ? i : i - peek() - 1;
max_area = Math.max(max_area, values[p] * width);
}
for(let i: number = 0; i < n; i++){
while(stack.length && values[i] < values[peek()]) update(i);
stack.push(i);
}
while(stack.length > 0) update(n);
return max_area;
}
console.log('Example:');
console.log(largestHistogram([5]));
// These "asserts" are used for self-checking
assert.equal(largestHistogram([5]), 5);
assert.equal(largestHistogram([5, 3]), 6);
assert.equal(largestHistogram([1, 1, 4, 1]), 4);
assert.equal(largestHistogram([1, 1, 3, 1]), 4);
assert.equal(largestHistogram([2, 1, 4, 5, 1, 3, 3]), 8);
console.log("Coding complete? Click 'Check' to earn cool rewards!");
Aug. 9, 2020
Comments:
