Largest Rectangle solution doesn't works
javaHelper opened this issue · 1 comments
javaHelper commented
Largest Rectangle solution doesn't works
Jivan2020 commented
import java.util.Stack;
public class Main {
public static void main(String[] args) {
// Define the histogram
int[] histogram = {6, 2, 5, 4, 5, 1, 6};
// Find the area of the largest rectangle
int maxArea = findLargestRectangle(histogram);
// Print the result
System.out.println("Largest rectangle: " + maxArea);
}
public static int findLargestRectangle(int[] histogram) {
// Create a stack to store the indices of the histogram bars
Stack stack = new Stack<>();
// Initialize variables
int maxArea = 0;
int i = 0;
// Iterate through the histogram bars
while (i < histogram.length) {
// If the stack is empty or the current bar is taller than the one on top of the stack, push the current bar's index onto the stack
if (stack.isEmpty() || histogram[i] >= histogram[stack.peek()]) {
stack.push(i++);
} else {
// Otherwise, calculate the area of the rectangle using the bar on top of the stack as the height
int height = histogram[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
int area = height * width;
// Update the maximum area if necessary
maxArea = Math.max(maxArea, area);
}
}
// Calculate the remaining rectangles in the stack
while (!stack.isEmpty()) {
int height = histogram[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
int area = height * width;
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
}