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
|
// 84. Largest Rectangle in Histogram
#include "leetcode.h"
/*
* given an array of integers 'heights' representing the histogram's bar height
* where the width of each bar is 1, return the area of the largest rectangle
*/
int area(int height, int width) { return height * width; }
int largestRectangleArea(int *heights, int heightsSize) {
int *stack = (int *)malloc((heightsSize + 1) * sizeof(int));
int stack_size = 0, max_area = 0;
for (int i = 0; i <= heightsSize; i++) {
int curr = i == heightsSize ? 0 : heights[i];
while (stack_size && curr < heights[stack[stack_size - 1]]) {
int pop_idx = stack[--stack_size];
int pop_height = heights[pop_idx];
int width = !stack_size ? i : i - stack[stack_size - 1] - 1;
max_area = fmax(max_area, area(pop_height, width));
}
stack[stack_size++] = i;
}
free(stack);
return max_area;
}
int main() {
int h1[] = {2, 1, 5, 6, 2, 3}, h2[] = {2, 4};
printf("%d\n", largestRectangleArea(h1, ARRAY_SIZE(h1))); // expect: 10
printf("%d\n", largestRectangleArea(h2, ARRAY_SIZE(h2))); // expect: 4
}
|