Largest Rectangle in Histogram LeetCode solution in C++

1
class Solution {
2
 private:
3
  vector<int> nextSmallerElement(vector<int> &arr, int n) {
4
    stack<int> s;
5
    s.push(-1);
6
    vector<int> ans(n);
7

8
    for (int i = n - 1; i >= 0; i--) {
9
      int curr = arr[i];
10

11
      while (s.top() != -1 && arr[s.top()] >= curr) {
12
        s.pop();
13
      }
14
      ans[i] = s.top();
15
      s.push(i);
16
    }
17
    return ans;
18
  }
19
  vector<int> prevSmallerElement(vector<int> &arr, int n) {
20
    stack<int> s;
21
    s.push(-1);
22
    vector<int> ans(n);
23

24
    for (int i = 0; i < n; i++) {
25
      int curr = arr[i];
26

27
      while (s.top() != -1 && arr[s.top()] >= curr) {
28
        s.pop();
29
      }
30
      ans[i] = s.top();
31
      s.push(i);
32
    }
33
    return ans;
34
  }
35

36
 public:
37
  int largestRectangleArea(vector<int> &heights) {
38
    int n = heights.size();
39
    int area = 1, ans = INT_MIN;
40

41
    vector<int> next(n);
42
    next = nextSmallerElement(heights, n);
43

44
    vector<int> prev(n);
45
    prev = prevSmallerElement(heights, n);
46

47
    for (int i = 0; i < n; i++) {
48
      int l = heights[i];
49

50
      if (next[i] == -1) {
51
        next[i] = n;
52
      }
53
      int b = next[i] - prev[i] - 1;
54

55
      area = l * b;
56
      ans = max(ans, area);
57
    }
58
    return ans;
59
  }
60
};