84. Largest Rectangle in Histogram

leetcode hard

#array#csharp#hard#leetcode#math

Task

Дан массив целых чисел heights, представляющий высоту столбцов гистограммы, где ширина каждого столбца равна 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.

C# solution

matched/original

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int max_area = 0;
        for (int i = 0; i < heights.Length; i++) {
            for (int j = i; j < heights.Length; j++) {
                int min_height = Int32.MaxValue;
                for (int k = i; k <= j; k++) {
                    min_height = Math.Min(min_height, heights[k]);
                }
                max_area = Math.Max(max_area, min_height * (j - i + 1));
            }
        }
        return max_area;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LargestRectangleArea(vector<int>& heights) {
        int max_area = 0;
        for (int i = 0; i < heights.size(); i++) {
            for (int j = i; j < heights.size(); j++) {
                int min_height = Int32.MaxValue;
                for (int k = i; k <= j; k++) {
                    min_height = min(min_height, heights[k]);
                }
                max_area = max(max_area, min_height * (j - i + 1));
            }
        }
        return max_area;
    }
}

Java solution

matched/original

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minheight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) minheight = Math.min(
                    minheight,
                    heights[k]
                );
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }
}

JavaScript solution

matched/original

var largestRectangleArea = function (heights) {
    let max_area = 0;
    for (let i = 0; i < heights.length; i++) {
        for (let j = i; j < heights.length; j++) {
            let min_height = Infinity;
            for (let k = i; k <= j; k++) {
                min_height = Math.min(min_height, heights[k]);
            }
            max_area = Math.max(max_area, min_height * (j - i + 1));
        }
    }
    return max_area;
};

Python solution

matched/original

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        max_area = 0
        for i in range(len(heights)):
            for j in range(i, len(heights)):
                min_height = inf
                for k in range(i, j + 1):
                    min_height = min(min_height, heights[k])
                max_area = max(max_area, min_height * (j - i + 1))
        return max_area

Go solution

matched/original

func largestRectangleArea(heights []int) int {
    max_area := 0
    inf := int(^uint(0) >> 1)
    for i := 0; i < len(heights); i++ {
        for j := i; j < len(heights); j++ {
            min_height := inf
            for k := i; k <= j; k++ {
                if heights[k] < min_height {
                    min_height = heights[k]
                }
            }
            if min_height*(j-i+1) > max_area {
                max_area = min_height * (j - i + 1)
            }
        }
    }
    return max_area
}

Explanation

Algorithm

1️⃣

Введение в проблему:

Прежде всего, следует учитывать, что высота прямоугольника, образованного между любыми двумя столбиками, всегда будет ограничена высотой самого низкого столбика, находящегося между ними. Это можно понять, взглянув на рисунок ниже.

2️⃣

Описание метода:

Таким образом, мы можем начать с рассмотрения каждой возможной пары столбиков и нахождения площади прямоугольника, образованного между ними, используя высоту самого низкого столбика между ними в качестве высоты и расстояние между ними в качестве ширины прямоугольника.

3️⃣

Вычисление максимальной площади:

Таким образом, мы можем найти требуемый прямоугольник с максимальной площадью.

😎