[leetcode]Maximal Rectangle @ Python [图解] [很难]
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[leetcode]Maximal Rectangle @ Python [图解] [很难],小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2666字,纯文字阅读大概需要4分钟。
内容图文
![[leetcode]Maximal Rectangle @ Python [图解] [很难]](/upload/InfoBanner/zyjiaocheng/1313/8175374c8b2b4bb589be1e31ff89c1b3.jpg)
原题地址: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]
.
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
.
解题思路:又是一道很巧妙的算法题。
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).
[最优解法] (下面提到的图2是制题目里面的第2个图)
class Solution: # @param height, a list of integer # @return an integer def largestRectangleArea(self, height): # 如图2所示,从左到右处理直方,当i = 4 时,小于当前栈顶(即直方3),对于直方3,无论后面还是前面的直方,都不可能得到比目前栈顶元素更高的高度了,处理掉直方3(计算从直方3到直方4 之间的矩形的面积,然后从栈里弹出);对于直方2 也是如此;直到碰到比直方4 更矮的直方1。这就意味着,可以维护一个递增的栈,每次比较栈顶与当前元素。如果当前元素小于栈顶元素,则入栈,否则合并现有栈,直至栈顶元素小于当前元素。 stack, area, i = [], 0, 0 height.append(0) while i < len(height): if stack == [] or height[i] > height[stack[-1]]: stack.append(i) i += 1 else: curr = stack.pop() width = i if stack == [] else i - (stack[-1] + 1) area = max(area, height[curr] * width) return area
这个是别人的解法,但是过于累赘。
class Solution: # @param height, a list of integer # @return an integer # @good solution! def largestRectangleArea(self, height): stack=[]; i=0; area=0 while 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]-1 area=max(area,width*height[curr]) i-=1 i+=1 while stack!=[]: curr=stack.pop() width=i if stack==[] else len(height)-stack[len(stack)-1]-1 area=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=0 for 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
原文:http://www.cnblogs.com/asrman/p/4001381.html
内容总结
以上是互联网集市为您收集整理的[leetcode]Maximal Rectangle @ Python [图解] [很难]全部内容,希望文章能够帮你解决[leetcode]Maximal Rectangle @ Python [图解] [很难]所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。