leetcode84

leetcode84

题目

avatar 意思是求能够构造出的矩形的面积有多大,题目很容易懂。

普通做法O(n^2)

这个很容易想到,因为最大的矩形的面积必定是以某个为高来弄的,那现在就把以每个为高的都算一次,就知道了。 比如依次是2, 6, 10, 6, 8, 3 意思是以2为高的就知道它一个,以1为高的底是6,以5为高的底是2, 以6为高的底是1, 以2为高的底是4, 以3为高的底是1。 所以很容易写出一个代码。 avatar 意思就是针对每一个高度,向左向右分别找到比它低的就停止,相当于找它能拓展的边界,比如高为5的时候,找到的l是1,r是2,那么底的长度就是(r-l-1)或可以理解成(r-l+1-2)即总长度去掉两个边。 然后更新就可以了。 所以这个复杂度是O(n^2)

O(n)的做法

avatar 这时候采用的是栈的方法,加上-1是为了判断是不是到最后了。 首先-1入栈,代表最左边的位置,然后当栈为空或者当前的高度比栈顶的高度要高的时候就入栈。 当栈不为空的时候且当前的高度比栈顶的要低的时候就出栈,出栈的时候要找左边那个界,因为这时候右边的这个界就是当前的位置。然后更新面积。这样感觉怪怪的,特别是算1的那个时候。

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦