Leetcode 84. Largest Rectangle in Histogram(python)

题目

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.

Example:
Input: [2,1,5,6,2,3]
Output: 10

解法1：Brutal force（TLE）

• 遍历所有interval
• 内部遍历interval记录minheight，并在每个位置计算maxarea

class Solution(object):def largestRectangleArea(self, heights):""":type heights: List[int]:rtype: int"""maxarea = 0n = len(heights)for i in range(n):minheight = float('inf')for j in range(i,n):minheight = min(minheight,heights[j])maxarea = max(maxarea,minheight*(j-i+1))return maxarea    

时间复杂度：O(n*n)
空间复杂度：O(1)

解法2：使用左右扫描线

• 对每个位置，分别探索向左能延伸到多远，向右能延伸到多远
• 相应位置形成rectangle的width就是向左延伸的距离加上向右延伸的距离，height便是当前位置的数字
• 为了加快向左和向右探索的速度，用left和right分别记录每个位置向左和向右能够探索的距离，left和right的长度与heights长度一致，这样就不需要每个位置去扫描，而可以跳着扫描

class Solution(object):def largestRectangleArea(self, heights):""":type heights: List[int]:rtype: int"""                 n = len(heights)left = [1]*nright = [1]*nfor i in range(n-2,-1,-1):if heights[i]<=heights[i+1]:j = i+1while j<n and heights[j]>=heights[i]:j += right[j]right[i] = j-ielse:continuefor i in range(1,n):if heights[i]<=heights[i-1]:j = i-1while j>=0 and heights[j]>=heights[i]:j -= left[j]left[i] = i-jmaxarea = 0for i in range(n):maxarea = max(heights[i]*(left[i]+right[i]-1),maxarea)return maxarea

时间复杂度：最差的时间复杂度应该是O(2*n^2+n),最好的情况是O(3n),但是提交结果只超过了百分之5的提交，证明这种方法并不理想
空间复杂度：O(n)

解法3：使用单调栈

使用一个单调递增栈来维护已经出现了的矩形高度

• 构建一个栈，如果当前元素比栈顶元素高，那么将该元素入栈
  否则，依次从栈顶开始弹出元素，直到找到比当前元素小的元素，这个时候栈顶元素为形成rectangle的左边界，当前所在位置为右边界，这样就可以算出当前rectangle面积
• 这样就可以通过从前向后遍历一遍heights就可以得到所有minarea，并从中挑出最大值
• 值得注意的有两点：1. 栈中保存的元素为heights中相应height的index，这样才可以一直能够计算相应的面积 2. 需要在heights后加入一个比所有height都小的值，否则的话，包括最后一个height在内的矩形面积便会被忽略

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

时间复杂度：O(n),提交结果超过了百分之九十的用户，说明这是个比较理想的解法
空间复杂度：O(n)