leetcode-javascript/solutions/0084-largest-rectangle-in-histogram.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Largest Rectangle In Histogram
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
var largestRectangleArea = function (histogramBars) {
    const numberBars = histogramBars.length;
    if (numberBars === 0) {
        return 0;
    }

    const leftBoundaryIndices = new Array(numberBars);
    const rightBoundaryIndices = new Array(numberBars);
    const indexStack = [];

    for (let iteratorIdx = 0; iteratorIdx < numberBars; iteratorIdx++) {
        while (indexStack.length > 0 && histogramBars[indexStack[indexStack.length - 1]] >= histogramBars[iteratorIdx]) {
            indexStack.pop();
        }
        if (indexStack.length === 0) {
            leftBoundaryIndices[iteratorIdx] = -1;
        } else {
            leftBoundaryIndices[iteratorIdx] = indexStack[indexStack.length - 1];
        }
        indexStack.push(iteratorIdx);
    }

    indexStack.length = 0;

    for (let iteratorIdx = numberBars - 1; iteratorIdx >= 0; iteratorIdx--) {
        while (indexStack.length > 0 && histogramBars[indexStack[indexStack.length - 1]] >= histogramBars[iteratorIdx]) {
            indexStack.pop();
        }
        if (indexStack.length === 0) {
            rightBoundaryIndices[iteratorIdx] = numberBars;
        } else {
            rightBoundaryIndices[iteratorIdx] = indexStack[indexStack.length - 1];
        }
        indexStack.push(iteratorIdx);
    }

    let maximumAchievedArea = 0;
    for (let iteratorIdx = 0; iteratorIdx < numberBars; iteratorIdx++) {
        const currentWidthCalc = rightBoundaryIndices[iteratorIdx] - leftBoundaryIndices[iteratorIdx] - 1;
        const potentialArea = histogramBars[iteratorIdx] * currentWidthCalc;
        if (potentialArea > maximumAchievedArea) {
            maximumAchievedArea = potentialArea;
        }
    }

    return maximumAchievedArea;
};