84. Largest Rectangle in Histogram
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.
Example:
Input: [2,1,5,6,2,3] Output: 10
Example 1:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4] Output: 4
Constraints:
1 <= heights.length <= 1050 <= heights[i] <= 104
Rust Solution
struct Solution;
impl Solution {
fn largest_rectangle_area(mut heights: Vec<i32>) -> i32 {
let mut stack: Vec<(i32, i32)> = vec![(0, 0)];
heights.push(0);
let n = heights.len();
let mut res = 0;
for i in 0..n {
let x1 = (i + 1) as i32;
let y1 = heights[i];
let mut x3 = x1;
while let Some(&(x2, y2)) = stack.last() {
if y2 > y1 {
stack.pop();
res = res.max((x1 - x2) * y2);
x3 = x2;
} else {
stack.push((x3, y1));
break;
}
}
}
res
}
}
#[test]
fn test() {
let heights = vec![2, 1, 5, 6, 2, 3];
let res = 10;
assert_eq!(Solution::largest_rectangle_area(heights), res);
let heights = vec![2, 1, 2];
let res = 3;
assert_eq!(Solution::largest_rectangle_area(heights), res);
}
Having problems with this solution? Click here to submit an issue on github.