В этой статье мы рассмотрим различные подходы к решению задачи поиска наибольшего прямоугольника на гистограмме с помощью языка программирования Java. Мы обсудим несколько методов, сопровождаемых примерами кода, которые помогут вам понять детали реализации. Итак, начнём!

Метод 1: перебор
Метод перебора предполагает рассмотрение каждого возможного прямоугольника на гистограмме и вычисление его площади. Мы перебираем каждый столбец гистограммы и рассматриваем его как начальную точку потенциального прямоугольника. Затем мы расширяем влево и вправо, вычисляя площадь прямоугольника, образованного текущим баром и соседними с ним барами. Наконец, мы отслеживаем максимальную встреченную площадь. Вот код:

public int largestRectangleArea(int[] heights) {
    int maxArea = 0;
    for (int i = 0; i < heights.length; i++) {
        int minHeight = Integer.MAX_VALUE;
        for (int j = i; j < heights.length; j++) {
            minHeight = Math.min(minHeight, heights[j]);
            int area = minHeight * (j - i + 1);
            maxArea = Math.max(maxArea, area);
        }
    }
    return maxArea;
}

Метод 2: использование стека
Этот метод использует стек для отслеживания индексов столбцов на гистограмме. Мы перебираем гистограмму и для каждого столбца сравниваем его высоту с высотой столбца наверху стека. Если текущий бар выше, мы помещаем его индекс в стек. В противном случае мы вычисляем площадь прямоугольника, образованного полосой наверху стека, и соответствующим образом обновляем максимальную площадь. Вот код:

import java.util.Stack;
public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0;
    int i = 0;
    while (i < heights.length) {
        if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
            stack.push(i);
            i++;
        } else {
            int top = stack.pop();
            int area = heights[top] * (stack.isEmpty() ? i : (i - stack.peek() - 1));
            maxArea = Math.max(maxArea, area);
        }
    }
    while (!stack.isEmpty()) {
        int top = stack.pop();
        int area = heights[top] * (stack.isEmpty() ? i : (i - stack.peek() - 1));
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

Метод 3: разделяй и властвуй
Этот подход применяет технику «разделяй и властвуй» для решения проблемы. Мы рекурсивно делим гистограмму на более мелкие подзадачи, находим максимальную площадь в каждой подзадаче и объединяем результаты. Основная идея состоит в том, чтобы найти минимальную высоту панели в текущем диапазоне и рассматривать ее как потенциальную высоту прямоугольника. Затем мы делим гистограмму на две части по индексу этого минимального столбца и рекурсивно применяем тот же процесс. Вот код:

public int largestRectangleArea(int[] heights) {
    return calculateArea(heights, 0, heights.length - 1);
}
private int calculateArea(int[] heights, int start, int end) {
    if (start > end) {
        return 0;
    }
    int minIndex = start;
    for (int i = start; i <= end; i++) {
        if (heights[i] < heights[minIndex]) {
            minIndex = i;
        }
    }
    int area = heights[minIndex] * (end - start + 1);
    int leftArea = calculateArea(heights, start, minIndex - 1);
    int rightArea = calculateArea(heights, minIndex + 1, end);
    return Math.max(area, Math.max(leftArea, rightArea));
}

В этой статье мы рассмотрели три различных метода поиска самого большого прямоугольника на гистограмме с помощью Java. Мы обсудили подход грубой силы, метод стека и технику «разделяй и властвуй». Каждый метод имеет свои плюсы и минусы, и выбор метода зависит от конкретных требований и ограничений решаемой задачи. Поняв эти методы и их реализацию, вы получите прочную основу для решения подобных проблем в будущем.