aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--largest_rectangle_histogram.c32
-rw-r--r--largest_rectangle_histogram.py30
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]))