diff options
author | Jack Sangdahl <[email protected]> | 2024-10-07 21:46:00 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-07 21:46:00 -0600 |
commit | a0b333f1632860075e8bee17784777ec002c2197 (patch) | |
tree | de2f032b08fceb77eb35e354ff08ea87a6cd9410 | |
parent | 2392e12d18162e1ad9083f4ec9f2498238302795 (diff) | |
download | leetcode-a0b333f1632860075e8bee17784777ec002c2197.tar.gz leetcode-a0b333f1632860075e8bee17784777ec002c2197.zip |
84. largest rectangle in histogram
-rw-r--r-- | largest_rectangle_histogram.c | 32 | ||||
-rw-r--r-- | largest_rectangle_histogram.py | 30 |
2 files changed, 62 insertions, 0 deletions
diff --git a/largest_rectangle_histogram.c b/largest_rectangle_histogram.c new file mode 100644 index 0000000..64680dc --- /dev/null +++ b/largest_rectangle_histogram.c @@ -0,0 +1,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 +} diff --git a/largest_rectangle_histogram.py b/largest_rectangle_histogram.py new file mode 100644 index 0000000..0b0853e --- /dev/null +++ b/largest_rectangle_histogram.py @@ -0,0 +1,30 @@ +# 84. Largest Rectangle in Histogram + +""" +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 +""" + + +class Solution(object): + def largestRectangleArea(self, heights): + """ + :type heights: List[int] + :rtype: int + """ + heights.append(0) + stack, ans = [-1], 0 + for i in range(len(heights)): + while heights[i] < heights[stack[-1]]: + h = heights[stack.pop()] + w = i - stack[-1] - 1 + ans = max(ans, h * w) + stack.append(i) + heights.pop() + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.largestRectangleArea(heights=[2, 1, 5, 6, 2, 3])) + print(obj.largestRectangleArea(heights=[2, 4])) |