Largest Rectangle in Histogram LeetCode solution in JavaScript

1
var largestRectangleArea = function (heights) {
2
  const n = heights.length;
3
  const nsr = new Array(n).fill(0);
4
  const nsl = new Array(n).fill(0);
5

6
  const stack = [];
7

8
  for (let i = n - 1; i >= 0; i--) {
9
    while (
10
      stack.length !== 0 &&
11
      heights[i] <= heights[stack[stack.length - 1]]
12
    ) {
13
      stack.pop();
14
    }
15
    if (stack.length === 0) {
16
      nsr[i] = n;
17
    } else {
18
      nsr[i] = stack[stack.length - 1];
19
    }
20
    stack.push(i);
21
  }
22

23
  while (stack.length !== 0) {
24
    stack.pop();
25
  }
26

27
  for (let i = 0; i < n; i++) {
28
    while (
29
      stack.length !== 0 &&
30
      heights[i] <= heights[stack[stack.length - 1]]
31
    ) {
32
      stack.pop();
33
    }
34
    if (stack.length === 0) {
35
      nsl[i] = -1;
36
    } else {
37
      nsl[i] = stack[stack.length - 1];
38
    }
39
    stack.push(i);
40
  }
41

42
  let ans = 0;
43

44
  for (let i = 0; i < n; i++) {
45
    ans = Math.max(ans, heights[i] * (nsr[i] - nsl[i] - 1));
46
  }
47

48
  return ans;
49
};