84. Largest Rectangle in Histogram

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;
    }
}

#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;
    }
}

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;
    }
}

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;
};

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

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️⃣

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

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

😎