LEETCODE，[leetcode]Largest Rectangle in Histogram @ Python

原題地址：https://oj.leetcode.com/problems/largest-rectangle-in-histogram/

題意：

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.

Above is a histogram where width of each bar is 1, given height =?[2,1,5,6,2,3].

LEETCODE、?

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

?

For example,
Given height =?[2,1,5,6,2,3],
return?10.

解題思路：又是一道很巧妙的算法題。

leetcodetop？Actually, we can decrease the complexity by using stack to keep track of the height and start indexes. Compare the current height with previous one.

Case 1: current > previous (top of height stack)
Push current height and index as candidate rectangle start position.

Case 2: current = previous
Ignore.

Case 3: current < previous
Need keep popping out previous heights, and compute the candidate rectangle with height and width (current index - previous index). Push the height and index to stacks.

(Note: it is better use another different example to walk through the steps, and you will understand it better).

代碼：

class Solution:# @param height, a list of integer# @return an integer# @good solution!def largestRectangleArea(self, height):maxArea = 0stackHeight = []stackIndex = []for i in range(len(height)):if stackHeight == [] or height[i] > stackHeight[len(stackHeight)-1]:stackHeight.append(height[i]); stackIndex.append(i)elif height[i] < stackHeight[len(stackHeight)-1]:lastIndex = 0while stackHeight and height[i] < stackHeight[len(stackHeight)-1]:lastIndex = stackIndex.pop()tempArea = stackHeight.pop() * (i-lastIndex)if maxArea < tempArea: maxArea = tempAreastackHeight.append(height[i]); stackIndex.append(lastIndex)while stackHeight:tempArea = stackHeight.pop() * (len(height) - stackIndex.pop())if tempArea > maxArea:maxArea = tempAreareturn maxArea

leetcode最長無重復字符串，?

代碼：

class Solution:# @param height, a list of integer# @return an integer# @good solution!def largestRectangleArea(self, height):stack=[]; i=0; area=0while i<len(height):if stack==[] or height[i]>height[stack[len(stack)-1]]:stack.append(i)else:curr=stack.pop()width=i if stack==[] else i-stack[len(stack)-1]-1area=max(area,width*height[curr])i-=1i+=1while stack!=[]:curr=stack.pop()width=i if stack==[] else len(height)-stack[len(stack)-1]-1area=max(area,width*height[curr])return area

常規解法，所有的面積都算一遍，時間復雜度O(N^2)。不過會TLE。

代碼：

class Solution:# @param height, a list of integer# @return an integer# @good solution!def largestRectangleArea(self, height):maxarea=0for i in range(len(height)):min = height[i]for j in range(i, len(height)):if height[j] < min: min = height[j]if min*(j-i+1) > maxarea: maxarea = min*(j-i+1)return maxarea

?