42. 接雨水

根据常识可以归纳出，对于每一列所能够存住的水的高度

Height = min(LeftMax, RightMax) - height

也就是，当前列的存水高度 = 左侧和右侧柱子的最大高度的较小值，减去当前列的柱子高度，所得到的差值。

可以验证第4列：Height = min(2, 3) - 1 = 1，其中2是最左边的最高的柱子（3列）高度，3是右边最高的柱子的高度（7列），1是当前4列的柱子的高度。

解法一：双指针

双指针解法主要的思想是牺牲空间换时间，也就是在最后遍历全部的柱子高度求解雨水高度之前，先把每一列所对应的最左边和最右边的最高的柱子算出来。因此需要两个for循环，循环前都需要进行初始化。

        leftmax[0] = height[0]
        for i in range(1, len(height)):
            leftmax[i] = max(height[i], leftmax[i-1])

        rightmax[len(height) - 1] = height[len(height) - 1]
        for i in range(len(height) - 2, -1, -1):
            rightmax[i] = max(height[i], rightmax[i+1])

至此，已经得到了每一列的左右最高的柱子，下面只需要遍历最后一次柱子，按照公式进行求解就可以了。 

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        # 双指针解法
        res  = 0
        leftmax = [0] * len(height)
        rightmax = [0] * len(height)

        leftmax[0] = height[0]
        for i in range(1, len(height)):
            leftmax[i] = max(height[i], leftmax[i-1])

        rightmax[len(height) - 1] = height[len(height) - 1]
        for i in range(len(height) - 2, -1, -1):
            rightmax[i] = max(height[i], rightmax[i+1])

        for i in range(len(height)):
            Height = min(leftmax[i], rightmax[i]) - height[i]
            if Height > 0:
                res += Height
        return res

解法二：单调栈

单调栈的性质是能够维护一个有顺序的高度索引的序列。

为什么是按照行来计算呢？

因为我们在一次操作中只能得到当前列（中间列）和左右两边列的高度，而不能得到左边最高值和右边最高值。

举个例子，对于列5（高度0），我们一次只能获取到列4（高度1）和列6（高度1），根据计算智能得到水位高度为1，但是因为看不到左右最高值，所以列5的上方是否还有水（列5的实际水位高度是2）就没有方法获取到。

单调栈解法的原理：

维护一个从栈底部到顶部为单调减高度的索引栈（栈的开口向右，可以想象成一个向右下的斜坡），那么在遍历到一个比栈顶元素大的元素的时候，恰好组成了一个V字，也就是中间低，两边高。这三个数字（栈顶、栈顶-1（左边的高度索引），遍历到的height（右边高度索引））就组成了一个储水的结构。

此时，只需要计算出左右索引之间的距离，在计算出左右索引对应的高度的最小值，即可得到储水的体积。

然后，栈顶的元素相当于被使用了，所以需要弹出，再判断当前遍历到的高度和新的栈顶元素的高度的大小（也就是之前的左侧的索引），最后，直到遍历到的元素比栈顶元素小（或者相等），再加入到栈中，组成一个递减的序列。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 单调栈解法
        res = 0
        stack = []
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                mid_height = stack.pop()  # 弹出来的是中间柱子的高度索引（作为最低的底部的高度）
                if stack:  # 确保当前的stack还有值，也就是左边界存在
                    h = min(height[stack[-1]], height[i]) - height[mid_height]
                    w = i - stack[-1] - 1
                    res += h * w
            stack.append(i)
        return res

84. 柱状图中最大的矩形

什么时候能够取到最大的矩形面积？

以一个柱子作为矩形高度的基准，向左向右遍历到的第一个比他小的柱子，作为矩形的左右边界，此时计算出的矩形面积是该柱子为最大高度基准时最大的。

2，2，3，4，5，4，3，3

蓝色边界的面积：3 * 5 = 15；

红色边界的面积：7 * 2 = 14；

所以可以确定，对于局部值而言，最大的面积在两侧第一个小于中心高度的区间之间。

解法一：双指针

对于本题，因为需要宽度，所以需要在双指针遍历的时候储存左右第一个小于当前高度值的索引。

        leftminidx[0] = -1
        for i in range(1, len(heights)):
            t = i - 1  # i左边的索引
            while t >= 0 and heights[i] <= heights[t]:
                t = leftminidx[t]
            leftminidx[i] = t

以左侧为例，因为需要向左侧拓展，如果一直比当前的柱子高度高，那么就将其索引值设置为自身，直到循环打破，储存第一个小于当前高度的索引。

这样做的好处是，在最后一次求解面积的遍历时，只需要进行面积的计算和结果的更新即可。

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """

        # 双指针解法
        res = 0

        leftminidx = [0] * len(heights)
        rightminidx = [0] * len(heights)

        leftminidx[0] = -1
        for i in range(1, len(heights)):
            t = i - 1  # i左边的索引
            while t >= 0 and heights[i] <= heights[t]:
                t = leftminidx[t]
            leftminidx[i] = t
        
        rightminidx[len(heights)-1] = len(heights)
        for i in range(len(heights)-2, -1, -1):
            t = i + 1
            while t <= len(heights) - 1 and heights[i] <= heights[t]:
                t = rightminidx[t]
            rightminidx[i] = t 

        for i in range(len(heights)):
            area = heights[i] * (rightminidx[i] - leftminidx[i] - 1)
            res = max(res, area)
        return res

解法二：单调栈

本题的分析上和接雨水相反，因为接雨水的栈结构实际上是构成了一个谷形来接住雨水，所以找的是第一个大于当前元素的值。但是本题实际上是构成一个山峰，所以需要找到的是第一个小于当前值的索引。

因此，单调栈的顺序是从栈底到栈顶递增。

每次遍历到的值（右边界）、栈顶元素（中间值）、栈顶元素的后一个值（左边界索引）构成了局部最大矩形。

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        # 单调栈解法
        res = 0
        stack = []
        heights.insert(0,0)  # 加上0防止溢出
        heights.append(0)  # 加上0防止溢出
        
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                mid_height = stack.pop()
                if stack:
                    Height = heights[mid_height]  # 中心值作为高度
                    Width = i - stack[-1] - 1  # 不算上两个边界索引
                    # print(stack)
                    res = max(res, Height * Width)
            stack.append(i)

        return res

Day54完结！！！