84. Largest Rectangle in Histogram Hard

1/**
2 * [84] Largest Rectangle in Histogram
3 *
4 * 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 in the histogram.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg" style="width: 522px; height: 242px;" />
8 * Input: heights = [2,1,5,6,2,3]
9 * Output: 10
10 * Explanation: The above is a histogram where width of each bar is 1.
11 * The largest rectangle is shown in the red area, which has an area = 10 units.
12 * 
13 * Example 2:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg" style="width: 202px; height: 362px;" />
15 * Input: heights = [2,4]
16 * Output: 4
17 * 
18 *  
19 * Constraints:
20 * 
21 * 	1 <= heights.length <= 10^5
22 * 	0 <= heights[i] <= 10^4
23 * 
24 */
25pub struct Solution {}
26
27// problem: https://leetcode.com/problems/largest-rectangle-in-histogram/
28// discuss: https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/?currentPage=1&orderBy=most_votes&query=
29
30// submission codes start here
31
32impl Solution {
33    pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
34        0
35    }
36}
37
38// submission codes end
39
40#[cfg(test)]
41mod tests {
42    use super::*;
43
44    #[test]
45    fn test_84() {
46    }
47}
48