| 9 | using namespace std; |
| 10 | |
| 11 | int maxHistogram(vector<int> v) |
| 12 | { |
| 13 | int maxArea = 0; // Initialize max area |
| 14 | int area = 0; // To store area with top bar as the smallest bar |
| 15 | int i; |
| 16 | int top; // To store top of stack |
| 17 | stack<int> s; |
| 18 | |
| 19 | // Run through all bars of given histogram |
| 20 | for(i=0;i<v.size();) |
| 21 | { |
| 22 | // If this bar is higher than the bar on top stack, push it to stack |
| 23 | if(s.empty() || v[i]>=v[s.top()]) |
| 24 | { |
| 25 | s.push(i++); |
| 26 | } |
| 27 | |
| 28 | // If this bar is lower than top of stack, then calculate area of rectangle with stack top as the smallest (or minimum height) bar. |
| 29 | else |
| 30 | { |
| 31 | top = s.top(); |
| 32 | s.pop(); |
| 33 | |
| 34 | // Calculate the area with hist[tp] stack as smallest bar |
| 35 | if(s.empty()) |
| 36 | area=v[top]*i; |
| 37 | else |
| 38 | area=v[top]*(i-s.top()-1); |
| 39 | |
| 40 | if(area>maxArea) |
| 41 | maxArea = area; |
| 42 | } |
| 43 | } |
| 44 | |
| 45 | // Pop the remaining bars from stack and calculate area with every popped bar as the smallest bar |
| 46 | while(s.empty() == false) |
| 47 | { |
| 48 | top = s.top(); |
| 49 | s.pop(); |
| 50 | if(s.empty()) |
| 51 | area=v[top]*i; |
| 52 | else |
| 53 | area=v[top]*(i-s.top()-1); |
| 54 | |
| 55 | if(area>maxArea) |
| 56 | maxArea = area; |
| 57 | } |
| 58 | return maxArea; |
| 59 | } |
| 60 | |
| 61 | int main() |
| 62 | { |