leetcode84. Largest Rectangle in Histogram

Harpsichord1207 發(fā)布于2019-08-15 10:55 / 1343人閱讀

摘要：題目要求即找到圖中可以組合而成的面積最大的矩形。從而我們可以知道該矩形在水平方向上的最大擴(kuò)展程度。也就是說，棧中數(shù)據(jù)記錄了最遠(yuǎn)左側(cè)下標(biāo)，而當(dāng)前的矩形則是最遠(yuǎn)右側(cè)下標(biāo)。當(dāng)我們不采用數(shù)據(jù)結(jié)構(gòu)時(shí)，尋找和計(jì)算的過程需要的時(shí)間復(fù)雜度。

題目要求

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.

即找到圖中可以組合而成的面積最大的矩形。

這里我首先想到的是leetcode 42 Trapping Rain Water，可以參考我的這篇博客。
因?yàn)樵?2題中，如果我找到了當(dāng)前矩形左右的最近最高矩形即可。而在本題中，同樣是需要找到該矩形左右的最高矩形，但不同的是，一旦我在左右搜尋的過程中遇到了一個(gè)比當(dāng)前矩形矮的矩形，遍歷即結(jié)束。所以兩道題目的要求還是存在區(qū)別的。

思路一：直觀但超時(shí)

最直觀的思路也就是從當(dāng)前矩形出發(fā)，分別向左向右遍歷，一旦遇到一個(gè)矩形比當(dāng)前矩形矮，則該方向的遍歷結(jié)束。從而我們可以知道該矩形在水平方向上的最大擴(kuò)展程度。代碼如下：

    public int largestRectangleArea(int[] heights) {
        int barCount = heights.length;
        
        int max = 0;
        for(int i = 0 ; i=0 && heights[j]>=tempHeight ; j--) tempWidth++;
            for(int j = i+1 ; j=tempHeight ; j++) tempWidth++;
            max = Math.max(max, tempWidth*tempHeight);
        }
        return max;
    }

當(dāng)然，該方法鑒于其需要O(n^2)的時(shí)間復(fù)雜度，再加上如果出現(xiàn)極端情況即每個(gè)矩形都可以水平擴(kuò)展至n長度，其中n等于數(shù)組的長度（例如[1,1,1,1,......,1],n=100000），這樣就會帶來很多無效的遍歷。

思路二：堆棧

如果我們按照順序從左往右遍歷，我們會返現(xiàn)，一旦右邊的矩形比左邊矮，則左邊矩形的向右擴(kuò)展的程度直接由右邊矩形決定。那么我們?nèi)绾沃雷筮吘匦蔚淖筮厰U(kuò)展程度呢。這就需要我們采用棧的模式來記錄。一旦新遇到的矩形比棧頂元素矮，我們需要逐個(gè)排出棧元素直到棧頂元素大于當(dāng)前矩形高度。同時(shí)我們還需要將當(dāng)前矩形的數(shù)據(jù)壓入棧中，而當(dāng)前矩形的左邊距則由排出的最后元素的下標(biāo)決定。也就是說，棧中數(shù)據(jù)記錄了最遠(yuǎn)左側(cè)下標(biāo)，而當(dāng)前的矩形則是最遠(yuǎn)右側(cè)下標(biāo)。代碼如下：

    public int largestRectangleArea2(int[] heights){
        int barCount = heights.length;
        int max = 0;
        LinkedList stack = new LinkedList();
        for(int i = 0 ; itempHeight){
                lastIndex = stack.pop();
                max = Math.max(max, (i-lastIndex)*heights[lastIndex]);
                heights[lastIndex] =tempHeight; 
            }
            stack.push(lastIndex);
        }
        while(!stack.isEmpty()){
            int currentIndex = stack.pop();
            max = Math.max(max, (barCount-currentIndex)*heights[currentIndex]);
        }
        return max;
    }

思路三：利用已有數(shù)據(jù)刪減遍歷

這里我們延續(xù)一種的思路，還是采用找到當(dāng)前矩形的最遠(yuǎn)左右側(cè)下標(biāo)，不同的是，我們用兩個(gè)數(shù)據(jù)結(jié)構(gòu)int[] lessFromLeft, int[] lessFromRight分別來存儲當(dāng)前矩形的最遠(yuǎn)左右側(cè)下標(biāo)。當(dāng)我們不采用數(shù)據(jù)結(jié)構(gòu)時(shí)，尋找和計(jì)算的過程需要O(n^2）的時(shí)間復(fù)雜度。而通過數(shù)據(jù)結(jié)構(gòu)，我們可以很大程度上減少遍歷次數(shù)，對當(dāng)前矩陣的最左側(cè)下標(biāo)可以通過lessFromLeft跳躍遍歷。也就是說，如果左側(cè)矩形比當(dāng)前矩形大，則跳到左側(cè)矩形的最左側(cè)矩形繼續(xù)判斷，如果最后調(diào)到起點(diǎn)，則結(jié)束遍歷。

代碼如下：

    public int largestRectangleArea3(int[] heights){
        int barCount = heights.length;
        if(barCount==0) return 0;
        int[] lessThanLeft = new int[barCount];
        int[] lessThanRight = new int[barCount];
        lessThanLeft[0] = -1;
        lessThanRight[barCount-1] = barCount;
        for(int i = 1 ; i=0 && heights[p]>=heights[i]){
                p = lessThanLeft[p];
            }
            lessThanLeft[i] = p;
        }
        for(int i = barCount-2 ; i>=0 ; i--){
            int p = i+1;
            while(p=heights[i]) p = lessThanRight[p];
            lessThanRight[i] = p;
        }
        
        int max = 0;
        for(int i = 0 ; i

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~