【LEETCODE】模拟面试-84-Largest Rectangle in Histogram

题目:

https://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 heights = [2,1,5,6,2,3], return 10.

分析:

This question is to get a maximum area of largest rectangle in the histogram.

Input is an array. Output is an int;

The brute force method is to scan its left side and right side for each bar, till the left boundary and right boundary which are lower than this bar. Then the area would be its height times index of right boundary minus left boundary. After all the bars are calculated, we can get the max area.

Another method is not to calculate the repeated work during the scanning. For example, when we scan the right side of bar_index=2( height=5 ), its right boundary is bar_index=4( height=2 ). And when we start to scan the left boundary for bar_index=4( height=2 ), in fact, we should already know bar_index=2( height=5 ) can cover this bar, so it will save time if we reduce the duplicate scanning, and store them in a data structure.

Here, we try to use stack to store such information.

  1. We scan from left to right.
  2. We add bar's index where might be the left boundary of its following bars, of course including current bar itself.
  3. We stop adding index as soon as we meet a bar which is lower then the height of top in the stack, since it means we have found the right boundary of the newest bar in the stack.
  4. Then we can start to calculate the possible area which are covered by the histogram determined by the stack.
  5. The formula is easy: (right boundary index - left boundary index) * current height reminder: the right boundary index is where the stack is stopped. the nearest left boundary is just the one bar in front of current bar. the height of a bar can be calculated in the bar is which is higher than both of its left AND right boundary.

For detail explanation can be found in code.

Java

public class Solution {

    public int largestRectangleArea(int[] heights){
    
        if ( heights == null || heights.length == 0 )
            return 0;
        
        Deque<Integer> stack = new LinkedList<Integer>();   //store index
        int max = 0;
        
        for ( int i = 0; i <= heights.length; i++ ){
            
            int curVal = (i == heights.length) ? 0 : heights[i];                //如果i到array的外面了,curVal=0,否则就为当前index装的高度
            
            while ( !stack.isEmpty() && heights[stack.peekLast()] >= curVal ){      //curVal 小于heights[stack.peekLast()],说明cur是最顶端一点的右边界
                                                                                    //如果 curVal 大于stack.peekLast(),说明这是cur的一个左边界
                                                                                    //stack里每个元素都是后一个元素的左边界,停止add的时候说明碰到了右边界
                int height = heights[stack.pollLast()];                             //pollLast get height(index) AND REMOVE index from stack
                int leftBound = stack.isEmpty() ? 0 : (stack.peekLast() + 1);       //注意 why +1: since pollLast() removed
                int rightBound = i;
                max = Math.max( max, height * (rightBound - leftBound) );           //用公式计算面积
            }       

            stack.addLast(i);                           //stack=[1,4]时,说明 1处比4处值小,但是2处被弹出去了,说明4处曾经是2处的右边界,4处相当于凹心
            
        }
        
        
        return max;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Hongten

Get the image file(s) some informations,Including the Make,Model,Date/Time,etc

This is a blog about how to get the image file(s) some informations.Including th...

10620
来自专栏高性能服务器开发

(三)dict哈希结构2

dict.c; /* Hash Tables Implementation. * * This file implements in memory ha...

27990
来自专栏Java架构师历程

jsoup解析的常见用法

1、解析attribute中值,如下面所示的serviceID和serviceName:

29630
来自专栏转载gongluck的CSDN博客

cocos2dx 连连看

#include "GameLink.h" #include "CountDownBar.h" USING_NS_CC; Scene* GameLink::...

33950
来自专栏高性能服务器开发

(五)sparkline微线图

sparkline这个单词,我第一次看的时候,也不知道这什么意思啊,以前根本没听过啊,但是这真真实实的出现在了redis的代码中了,刚刚开始以为这也是属于普通...

393120
来自专栏机器学习与自然语言处理

03-树3. Tree Traversals Again (25)将先序遍历和中序遍历转为后序遍历

03-树3. Tree Traversals Again (25) 题目来源:http://www.patest.cn/contests/mooc-ds/03-...

35490
来自专栏码匠的流水账

聊聊flink的CheckpointScheduler

flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/checkpoint/Checkp...

18830
来自专栏Java学习网

Java实现把整数转换为英语单词的方法,实用代码

一个非负整数转换为英文单词表示。 例如: 123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand...

25390
来自专栏葡萄城控件技术团队

深入浅出OOP(三): 多态和继承(动态绑定/运行时多态)

在前面的文章中,我们介绍了编译期多态、params关键字、实例化、base关键字等。本节我们来关注另外一种多态:运行时多态, 运行时多态也叫迟绑定。 运行时多态...

20480
来自专栏码匠的流水账

聊聊storm的IWaitStrategy

storm-2.0.0/storm-client/src/jvm/org/apache/storm/policy/IWaitStrategy.java

8210

扫码关注云+社区

领取腾讯云代金券