@@ -0,0 +1,1977 @@
+/***%0A * 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.%0A *%0A *%0A * Above is a histogram where width of each bar is 1, given height = %5B2,1,5,6,2,3%5D.%0A *%0A *%0A * The largest rectangle is shown in the shaded area, which has area = 10 unit.%0A *%0A * For example,%0A * Given height = %5B2,1,5,6,2,3%5D,%0A * return 10.%0A */%0Aimport java.util.Stack;%0Apublic class Solution %7B%0A    // Solution 1: O(n%5E2), Exceed time limit.%0A    // For each pair of bars, calculate area.%0A%0A    // Solution 2: O(n%5E2)%0A    // Expand to left, only when current one is bigger than previous %0A    public int largestRectangleArea(int%5B%5D height) %7B%0A        int maxV = 0;%0A        for (int i = 0; i %3C height.length; i++) %7B%0A            if (i + 1 %3C height.length && height%5Bi%5D %3C height%5Bi + 1%5D)%0A                continue;%0A            int minV = height%5Bi%5D;%0A            for (int j = i; j %3E= 0; j--) %7B%0A                minV = Math.min(minV, height%5Bj%5D);%0A                int area = minV * (i - j + 1);%0A                if (area %3E maxV)%0A                    maxV = area;%0A            %7D%0A        %7D%0A        return maxV;%0A    %7D%0A%0A    // Solution 3: O(n)%0A    // Maintain a monotonically increasing height stack,%0A    // If meet a bar has a lower height, then calculate the areas%0A    // of bars higher than it.%0A    // Add 0 to bar height array to do calculation for all values%0A    public int largestRectangleArea(int%5B%5D height) %7B%0A        Stack%3CInteger%3E stk = new Stack%3CInteger%3E();%0A        int ret = 0;%0A        int %5B%5D h = new int%5Bheight.length + 1%5D;%0A        h = Arrays.copyOf(height, height.length + 1);%0A        for (int i = 0; i %3C h.length; ) %7B%0A            if (stk.isEmpty() %7C%7C h%5Bi%5D %3E h%5Bstk.peek()%5D)%0A                stk.add(i++);%0A            else %7B%0A                int temp = stk.pop();%0A                ret = Math.max(ret, %0A                        h%5Btemp%5D * (stk.isEmpty() ? i : i - stk.peek() - 1));%0A            %7D%0A        %7D%0A        return ret;%0A    %7D%0A%7D%0A

add LargestRectangleinHistogram.java