forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
largestRectangleInHistogram.cpp
81 lines (72 loc) · 1.92 KB
/
largestRectangleInHistogram.cpp
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Source : https://oj.leetcode.com/problems/largest-rectangle-in-histogram/
// Author : Hao Chen
// Date : 2014-07-20
/**********************************************************************************
*
* Given n non-negative integers representing the histogram's bar height where the width of each bar is 1,
* find the area of largest rectangle in the histogram.
*
* Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
*
* The largest rectangle is shown in the shaded area, which has area = 10 unit.
*
* For example,
* Given height = [2,1,5,6,2,3],
* return 10.
*
*
**********************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
int largestRectangleArea(vector<int> &height) {
if (height.size()<=0) return 0;
vector<int> stack;
height.push_back(0);
int maxArea = 0;
for(int i=0; i<height.size(); i++){
if ( stack.size()<=0 || height[i] >= height[stack.back()] ) {
stack.push_back(i);
continue;
}
int topIdx = stack.back();
stack.pop_back();
int area = height[topIdx] * (stack.size()==0 ? i : i - stack.back() - 1 );
if ( area > maxArea ) {
maxArea = area;
}
i--;
}
return maxArea;
}
void printArray(vector<int> &v)
{
cout << "{";
for(int i=0; i<v.size(); i++) {
cout << " " << v[i];
}
cout << "}" << endl;
}
void test(int a[], int n)
{
vector<int> v(a, a + n);
printArray(v);
cout << largestRectangleArea(v) << endl;
}
int main()
{
#define TEST(a) test(a, sizeof(a)/sizeof(int))
int a0[] = {2,1,3,1};
TEST(a0);
int a1[] = {2,1,5,6,2,3};
TEST(a1);
return 0;
}
/*int main()
{
int a[] = {2,1,5,6,2,3};
vector<int> v(a, a + sizeof(a)/sizeof(int));
printArray(v);
cout << largestRectangleArea(v) << endl;
return 0;
}*/