The histogram is a graphical representation of data in the form of bars or rectangles. each bar corresponds to the range or frequency of data.
package org.wesome.dsalgo;
import java.util.Stack;
public class HistogramHeight {
public static int histogramHeight(int arr[]) {
int lengths = arr.length;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int max_area = arr[0];
int left_smaller[] = new int[lengths];
int right_smaller[] = new int[lengths];
for (int i = 0; i < lengths; i++) {
left_smaller[i] = -1;
right_smaller[i] = lengths;
}
int i = 0;
while (i < lengths) {
while (!stack.empty() && stack.peek() != -1 && arr[i] < arr[stack.peek()]) {
right_smaller[stack.peek()] = i;
stack.pop();
}
if (i > 0 && arr[i] == arr[(i - 1)]) {
left_smaller[i] = left_smaller[i - 1];
} else {
left_smaller[i] = stack.peek();
}
stack.push(i);
i++;
}
for (i = 0; i < lengths; i++) {
max_area = Math.max(max_area, arr[i] * (right_smaller[i] - left_smaller[i] - 1));
}
return max_area;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
public class HistogramHeightTest {
@Test
void histogramHeightTest1() {
int histogramHeights[] = {6, 2, 5, 4, 5, 1, 6};
Assertions.assertEquals(12, HistogramHeight.histogramHeight(histogramHeights));
}
}
plugins {
id 'java'
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}