Algorithms/Largest_Rectangle_in_Histogram.cpp at main · giyasht/Algorithms · 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
53
54
55
56
57
58
59
class Solution
{
public:
    vector<int> leftindex(vector<int> arr, int n)
    {
        stack<int> s;
        s.push(-1);
        vector<int> v(n);
        for (int i = 0; i < n; i++)
        {
            int curr = arr[i];
            while (s.top() != -1 && arr[s.top()] >= curr)
            {
                s.pop();
            }
            v[i] = s.top();
            s.push(i);
        }
        return v;
    }
    vector<int> rightindex(vector<int> arr, int n)
    {
        stack<int> s;
        s.push(-1);
        vector<int> v(n);
        for (int i = n - 1; i >= 0; i--)
        {
            int curr = arr[i];
            while (s.top() != -1 && arr[s.top()] >= curr)
            {
                s.pop();
            }
            v[i] = s.top();
            s.push(i);
        }
        return v;
    }
    int largestRectangleArea(vector<int> &heights)
    {
        int n = heights.size();
        vector<int> left(n);
        left = leftindex(heights, n);
        vector<int> right(n);
        right = rightindex(heights, n);
        int area = INT_MIN;
        for (int i = 0; i < n; i++)
        {
            int l = heights[i];
            if (right[i] == -1)
            {
                right[i] = n;
            }
            int b = right[i] - left[i] - 1;
            int newarea = l * b;
            area = max(area, newarea);
        }
        return area;
    }
};