Lexi's Leetcode solutions

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.

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

这个也是看别人答案做出来的。感觉很像那道二维直方图盛水的题，可惜那道是短板固定在两边，这题则是短板可以随意在中间任何一个位置。总之，这种题一定能找到一个状态，就是在i之前，i怎么变都是越来越大（小），但是在i处就不一定了，所以对i才进行运算，之前的就不用算了反正都是比算i的小（大）。

算法：

穷举两个边界，但不是完全穷举，这里可以省掉一部分右右边界。对于i，如果A[i] <= A[i + 1]，即当前递增，则无论对于哪个左边界，选i+1作为右边界都比选i作为右边界合适（宽本来就多一个，然后高还更高，所以肯定选右边的面积大）。所以就算i+1作为右边界的所有左边界配对就行，没必要算i作为右边界的了。所以递推下去，只有A[i] > A[i + 1]的时候，在递减，说明拿A[i]和拿A[i + 1]不一定谁大了，这时候算一下A[i]作为右边界的左边界所有可能，就是一个local peak。这题还有一个O(n)的解法，但是暂时懒的看了。下次再看。

public int largestRectangleArea(int[] height) {
    int res = 0;
    for (int i = height.length - 1; i >= 0; i--) {
        if (i == height.length - 1 || height[i] > height[i + 1]) { //A[i] is a local peak
            int min = Integer.MAX_VALUE;
            for (int j = i; j >= 0; j--) {
                min = Math.min(min, height[j]);
                res = Math.max(res, (i - j + 1) * min);
            }
        }
    }
    return res;
}