Programming/histogram.cpp at master · arshdeep/Programming · 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
#include<iostream>
#include<limits.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;

int largestRectangleArea(vector<int>& height) {
    stack<int> stk;
    int res = 0;
    int i = 0, n = height.size();

    while( i < n) {
        if (stk.empty() || height[i] >= height[stk.top()]) {
            stk.push(i++);
        }
        else {
            int top = stk.top();
            stk.pop();

            res = std::max( res, height[top] * (stk.empty() ? i : i - stk.top() - 1) );
        }
    }

    while ( !stk.empty() ) {
        int top = stk.top();
        stk.pop();

        res = std::max( res, height[top] * (stk.empty() ? i : i - stk.top() - 1) );
    }
    return res;
}

// Driver program to test above function
int main()
{
    vector<int> vect;

	vect.push_back(2);
	vect.push_back(1);
	vect.push_back(5);
	vect.push_back(6);

	vect.push_back(4);
	vect.push_back(3);
	cout<<largestRectangleArea(vect);
    getchar();
    return 0;
}