84. Largest Rectangle in Histogram

LeetCode hard оригинал: C# #array #csharp #hard #leetcode #math

Дан массив целых чисел 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# решение

сопоставлено/оригинал
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++ решение

auto-draft, проверить перед отправкой
#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 решение

сопоставлено/оригинал
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 решение

сопоставлено/оригинал
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 решение

сопоставлено/оригинал
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 решение

сопоставлено/оригинал
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
}

Algorithm

1️⃣

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

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

2️⃣

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

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

3️⃣

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии
Активных вакансий пока нет.