国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[leetcode]85. Maximal Rectangle

stackvoid / 449人閱讀

摘要:對于一個矩形,可以用最高可能的高度來唯一標(biāo)記該矩形。剩下的寬度由該最高高度所表示矩形的最左邊界和最右邊界得出。

Given a 2D binary matrix filled with 0"s and 1"s, find the largest rectangle containing only 1"s and return its area.
For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

return 6

對于一個矩形,可以用最高可能的高度來唯一標(biāo)記該矩形。剩下的寬度由該最高高度所表示矩形的最左邊界和最右邊界得出。
height:
1 0 1 0 0
2 0 2 1 1
3 1 3 2 2
4 0 0 3 0

left:
0 0 2 0 0
0 0 2 2 2
0 0 2 2 2
0 0 0 3 0

right:
1 5 3 5 5
1 5 3 5 5
1 5 3 5 5
1 5 5 4 5

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if(matrix == null || m == 0) return 0;
         int n = matrix[0].length;
        int maxA = 0;
        int[] right = new int[n], left = new int[n], heights = new int[n];  // rectangle with highest height
        Arrays.fill(right,n);
        
        for(int i=0; i=0;j--) {
                if(matrix[i][j] == "1") right[j] = Math.min(curright, right[j]);
                else{ right[j] = n; curright = j; }         // remain at last zero position
            }
            for(int j=0; j           
               
                                           
                       
                 

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66281.html

相關(guān)文章

  • leetcode85. Maximal Rectangle

    摘要:題目要求輸入一個二維數(shù)組,其中代表一個小正方形,求找到數(shù)組中最大的矩形面積。思路一用二維數(shù)組存儲臨時值的一個思路就是通過存儲換效率。從而省去了許多重復(fù)遍歷,提高效率。這里我使用兩個二維數(shù)組來分別記錄到為止的最大長度和最大高度。 題目要求 Given a 2D binary matrix filled with 0s and 1s, find the largest rectangle ...

    jhhfft 評論0 收藏0
  • 85. Maximal Rectangel

    摘要:題目解答這題思路很重要,一定要理清和的參數(shù)之間的關(guān)系,那么就事半功倍了。表示從左往右到,出現(xiàn)連續(xù)的的第一個座標(biāo),表示從右往左到出現(xiàn)連續(xù)的的最后一個座標(biāo),表示從上到下的高度。見上述例子,保證了前面的數(shù)組是正方形且沒有的最小矩形, 題目:Given a 2D binary matrix filled with 0s and 1s, find the largest rectangle co...

    Corwien 評論0 收藏0
  • [Leetcode] Largest Rectangle (in Histogram) 最大矩形

    摘要:以此類推,如果一直到棧為空時,說明剛出來的豎條之前的所有豎條都比它自己高,不然不可能棧為空,那我們以左邊全部的寬度作為長方形的寬度。 Largest Rectangle in Histogram Given n non-negative integers representing the histograms bar height where the width of each bar...

    鄒強(qiáng) 評論0 收藏0
  • [LintCode/LeetCode] Maximal Square

    摘要:類似這種需要遍歷矩陣或數(shù)組來判斷,或者計算最優(yōu)解最短步數(shù),最大距離,的題目,都可以使用遞歸。 Problem Given a 2D binary matrix filled with 0s and 1s, find the largest square containing all 1s and return its area. Example For example, given t...

    Drinkey 評論0 收藏0
  • [Leetcode] Maximal Square 最大正方形

    摘要:但如果它的上方,左方和左上方為右下角的正方形的大小不一樣,合起來就會缺了某個角落,這時候只能取那三個正方形中最小的正方形的邊長加了。假設(shè)表示以為右下角的正方形的最大邊長,則有當(dāng)然,如果這個點在原矩陣中本身就是的話,那肯定就是了。 Maximal Square Given a 2D binary matrix filled with 0s and 1s, find the larges...

    xiaowugui666 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<