1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 6, 2015
4+ Problem: Largest Rectangle in Histogram
5+ Difficulty: Hard
6+ Source: https://oj.leetcode.com/problems/largest-rectangle-in-histogram/
7+ Notes:
8+ Given n non-negative integers representing the histogram's bar height where the width of each
9+ bar is 1, find the area of largest rectangle in the histogram.
10+ For example,
11+ Given height = [2,1,5,6,2,3],
12+ return 10.
13+
14+ Solution: 1. Only calucate area when reaching local maximum value.
15+ 2. Keep a non-descending stack. O(n). if the vector height is not allowed to be changed.
16+ */
17+ public class Solution {
18+ public int largestRectangleArea_1 (int []height ) {
19+ int res =0 ;
20+ for (int i =0 ;i <height .length ; ++i ) {
21+ if ((i <height .length -1 ) && (height [i ] <=height [i +1 ])) {
22+ continue ;
23+ }
24+ int minheight =height [i ];
25+ for (int j =i ;j >=0 ; --j ) {
26+ minheight =Math .min (minheight ,height [j ]);
27+ res =Math .max (res , (i -j +1 )*minheight );
28+ }
29+ }
30+ return res ;
31+ }
32+ public int largestRectangleArea (int []height ) {
33+ int res =0 ;
34+ Stack <Integer >stk =new Stack <Integer >();
35+ int i =0 ;
36+ while (i <height .length ) {
37+ if (stk .isEmpty () ==true || (height [i ] >=height [stk .peek ()])) {
38+ stk .push (i ++);
39+ }else {
40+ int idx =stk .pop ();
41+ int width =stk .isEmpty () ?i : (i -stk .peek () -1 );
42+ res =Math .max (res ,width *height [idx ]);
43+ }
44+ }
45+ while (stk .isEmpty () ==false ) {
46+ int idx =stk .pop ();
47+ int width =stk .isEmpty () ?height .length : (height .length -stk .peek () -1 );
48+ res =Math .max (res ,width *height [idx ]);
49+ }
50+ return res ;
51+ }
52+ }
