/
NikolayIvkin
/
TheAlgorithms
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/main/java/com/thealgorithms/stacks/LargestRectangle.java
38 строк
1 KB
Alex Klymenko
style: use proper spelling (#5436)
30 авг 2024, 09:50
Не верифицирован
30 авг 2024, 09:50
87cf891
Код
Авторство
О чём код?
package com.thealgorithms.stacks; import java.util.Stack; /** * * @author mohd rameez github.com/rameez471 */ public final class LargestRectangle { private LargestRectangle() { } public static String largestRectangleHistogram(int[] heights) { int n = heights.length; int maxArea = 0; Stack<int[]> st = new Stack<>(); for (int i = 0; i < n; i++) { int start = i; while (!st.isEmpty() && st.peek()[1] > heights[i]) { int[] tmp = st.pop(); maxArea = Math.max(maxArea, tmp[1] * (i - tmp[0])); start = tmp[0]; } st.push(new int[] {start, heights[i]}); } while (!st.isEmpty()) { int[] tmp = st.pop(); maxArea = Math.max(maxArea, tmp[1] * (n - tmp[0])); } return Integer.toString(maxArea); } public static void main(String[] args) { assert largestRectangleHistogram(new int[] {2, 1, 5, 6, 2, 3}).equals("10"); assert largestRectangleHistogram(new int[] {2, 4}).equals("4"); } }