FilesExpand file tree

 master

/

LargestRectangleinHistogram.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

34 lines (32 loc) · 973 Bytes

 master

/

LargestRectangleinHistogram.java

Copy path

Top

File metadata and controls

• Code
• Blame

34 lines (32 loc) · 973 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

import java.util.Arrays;

import java.util.Stack;

/**

* Given n non-negative integers representing the histogram's bar height where

* the width of each bar is 1, find the area of largest rectangle in the

* histogram.

*

* Above is a histogram where width of each bar is 1, given height =

* [2,1,5,6,2,3].

*

* The largest rectangle is shown in the shaded area, which has area = 10 unit.

*

* For example, Given height = [2,1,5,6,2,3], return 10.

*/

public class LargestRectangleinHistogram {

public int largestRectangleArea(int[] height) {

Stack<Integer> stack = new Stack<Integer>();

int i = 0;

int maxArea = 0;

int[] h = new int[height.length + 1];

h = Arrays.copyOf(height, height.length + 1);

while (i < h.length) {

if (stack.isEmpty() || h[stack.peek()] <= h[i]) {

stack.push(i++);

} else {

int t = stack.pop();

maxArea = Math.max(maxArea, h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));

}

}

return maxArea;

}

}