前言：
此刻看官们对“坐在马桶上看算法6”大致比较着重，小伙伴们都想要分析一些“坐在马桶上看算法6”的相关资讯。那么小编也在网摘上收集了一些有关“坐在马桶上看算法6””的相关内容，希望朋友们能喜欢，小伙伴们一起来学习一下吧！题目：题目描述：
给一个数组，数组中的所有元素均是非负数，数组下标和数组元素（即：(i,arr[i])）可以理解点，求这些点与x轴围成的最大矩形面积。
题目有点绕口，看题目下面这个例子，
input：数组 height=[1,8,6,2,5,4,8,3,7];
output：49；
解释：7*（8-1）=49； （参见下图：最大面积刚好是蓝色的区域）
思路：
要使得矩形的面积最大，则必须要width和height尽可能的大。这里我们把左边界用left表示，把右边界用right表示。 则有
width=right-left
height=min(height[left] ,heght[right]) ———不理解的话可以想一下“木桶效应”（木桶效应：简单来说就是在不倾斜的前提下短板决定水桶的容量）
解决方案 ( 暴力破解和双指针) 暴力法：
public int maxAreaWithViolent(int[] height) { int maxArea = 0; for (int left = 0; left < height.length; left++) for (int right = left + 1; right < height.length; right++) maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left)); return maxArea; }分析：时间复杂度O(n*n)，空间复杂度O(1)
双指针法：
public int maxAreaWithDoublePointer(int[] height) { int maxArea=0; int left=0; int right=height.length-1; while(left<right) { maxArea=Math.max(maxArea, Math.min(height[left], height[right])*(right-left)); if (height[left]<height[right]) left++; else right--; } return maxArea; }分析：时间复杂度O(n), 空间复杂度O(1)
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #坐在马桶上看算法6
