rectangle area

jhideki · jhideki · commit 42aa4426c77f · 2024-02-19T12:47:59.000-08:00
diff --git a/src/largest_histogram.rs b/src/largest_histogram.rs
@@ -0,0 +1,29 @@
+pub struct Solution {}
+
+impl Solution {
+    pub fn largest_area(heights: Vec<i32>) -> i32 {
+        let mut largest_area: i32 = 0;
+        let mut stack: Vec<(usize, i32)> = Vec::new();
+        for i in 0..heights.len() {
+            let mut start = i;
+            while !stack.is_empty() && heights[i] < stack.last().unwrap().1 {
+                let val = stack.pop().unwrap();
+                let area = val.1 * (i - val.0) as i32;
+                if area > largest_area {
+                    largest_area = area;
+                }
+                start = val.0;
+            }
+            stack.push((start, heights[i]));
+        }
+
+        for val in stack {
+            let area = (heights.len() - val.0) as i32 * val.1;
+            if area > largest_area {
+                largest_area = area;
+            }
+        }
+
+        largest_area
+    }
+}
diff --git a/src/main.rs b/src/main.rs
@@ -1,7 +1,7 @@
-mod trapping_rain_water;
-use trapping_rain_water::Solution;
+mod largest_histogram;
+use largest_histogram::Solution;
 fn main() {
-    let heights = vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
-    let result = Solution::rain_water(heights);
+    let heights = vec![2, 1, 5, 6, 2, 3];
+    let result = Solution::largest_area(heights);
     print!("{:?}", result);
 }
