42. 接雨水

• 题目链接：42. 接雨水
• 双指针

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        lh = [0]*len(height)
        rh = [0]*len(height)
        
        lh[0]=height[0]
        for i in range(1, len(height)):
            lh[i] = max(height[i],lh[i-1])
        rh[-1]=height[-1]
        for j in range(len(height)-2, -1, -1):
            rh[j] = max(height[j], rh[j+1])
        
        result = 0
        for k in range(len(height)):
            result += min(lh[k], rh[k])-height[k]
        
        return result

• 单调栈

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

        for i in range(1, len(height)):
            if height[i]<height[stack[-1]]:
                stack.append(i)
            elif height[i]==height[stack[-1]]:
                stack.pop()
                stack.append(i)
            else:
                while stack and height[i]>height[stack[-1]]:
                    sub = height[stack[-1]]
                    stack.pop()
                    if stack:
                        h = min(height[stack[-1]], height[i])-sub
                        w = i-stack[-1]-1
                        result+=w*h
                stack.append(i)

        return result

84.  柱状图中最大的矩形

• 题目链接：84.  柱状图中最大的矩形
• 为什么要首尾加零：防止单调递增递减序列的情况

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        heights.insert(0,0)
        heights.append(0)
        result = 0
        stack = [0]
        
        for i in range(1, len(heights)):
            if heights[i]>heights[stack[-1]]:
                stack.append(i)
            elif heights[i]==heights[stack[-1]]:
                stack.pop()
                stack.append(i)
            else:
                while stack and heights[i]<heights[stack[-1]]:
                    mid_index = stack[-1]
                    stack.pop()
                    if stack:
                        w = i-stack[-1]-1
                        h = heights[mid_index]
                        result = max(result, w*h)
                stack.append(i)
        return result