Skip to content

Added a stack algorithm- find largest rectangle in histogram #243

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 1 commit into from
Closed

Added a stack algorithm- find largest rectangle in histogram #243

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
60 changes: 60 additions & 0 deletions data_structures/Stacks/LargestRectAreaInHistogram.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,60 @@
package Stacks;

import java.util.Stack;

public class LargestRectAreaInHistogram {

static int findMaxArea(int hist[], int n) {
Stack<Integer> stack = new Stack<Integer>();
int max_area = 0;
int top;
int currentAreaSoFar;

// Run through all bars of given histogram
int i = 0;
while (i < n) {
// If this bar is longer then stack.push
if (stack.empty() || hist[stack.peek()] <= hist[i])
stack.push(i++);

// If this bar is lower than top of stack, then calculate area of
// rectangle
// with stack top as the smallest (or minimum height) bar. 'i' is
// 'right index' for the top and element before top in stack is
// 'left index'
else {
top = stack.peek(); // store the top index
stack.pop(); // pop the top

// Calculate the area with hist[tp] stack as smallest bar
currentAreaSoFar = hist[top]
* (stack.empty() ? i : i - stack.peek() - 1);

// update max area, if needed
if (max_area < currentAreaSoFar)
max_area = currentAreaSoFar;
}
}

// Now pop the remaining bars from stack and calculate area with every
// popped bar as the smallest bar
while (stack.empty() == false) {
top = stack.peek();
stack.pop();
currentAreaSoFar = hist[top]
* (stack.empty() ? i : i - stack.peek() - 1);

if (max_area < currentAreaSoFar)
max_area = currentAreaSoFar;
}
return max_area;

}

// main method to test
public static void main(String[] args) {
int hist[] = { 5, 4, 9, 6 };
System.out.println("Maximum area of a rectangle possible is "
+ findMaxArea(hist, hist.length));
}
}