LeetCode問題解(100):Maximal Rectangle

タイトル:
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
問題:
Largest Rectangle in Histogramの神算法をベースに少し変更すればよい.
c++版:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() == 0)
            return 0;
        vector<int> height(matrix[0].size());
        int maxArea = 0;
        for(int i = 0; i < matrix.size(); i++) {
            for(int j = 0; j < matrix[0].size(); j++) {
                if(matrix[i][j] == '0')
                    height[j] = 0;
                else
                    height[j] = height[j] + 1;
            }
            int cur = maximalArea(height);
            if(cur > maxArea)
                maxArea = cur;
        }
        return maxArea;
    }
    
    int maximalArea(vector<int>& height) {
        height.push_back(0);
        stack<int> index;
        int maxArea = 0;
        int i = 0;
        while(i < height.size()) {
            if(index.size() == 0 || height[index.top()] <= height[i])
                index.push(i++);
            else {
                int t = index.top();
                index.pop();
                maxArea = max(maxArea, height[t] * (index.size() == 0 ? i : i - 1 - index.top()));
            }
        }
        return maxArea;
    }
};

Java版:

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0)
            return 0;
        
        int[] height = new int[matrix[0].length];
        int maxArea = 0;
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == '0')
                    height[j] = 0;
                else
                    height[j] += 1;
            }
            int cur = largestRectangleArea(height);
            if(cur > maxArea)
                maxArea = cur;
        }
        return maxArea;
    }
    
    public int largestRectangleArea(int[] height) {  
        int[] h = new int[height.length + 1];  
        h = Arrays.copyOf(height, height.length + 1);  
        Stack<Integer> index = new Stack<>();  
        int i = 0;  
        int maxArea = 0;  
        while(i < h.length) {  
            if(index.isEmpty() || h[index.peek()] <= h[i]) {  
                index.push(i++);  
            } else {  
                int t = index.pop();  
                maxArea = Math.max(maxArea, h[t] * (index.isEmpty() ? i : i - 1 - index.peek()));  
            }  
        }  
        return maxArea;  
    }  
}

Python版:

class Solution:
    # @param {character[][]} matrix
    # @return {integer}
    def maximalRectangle(self, matrix):
        if len(matrix) == 0:
            return 0
        height = [0] * len(matrix[0])
        maxArea = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '0':
                    height[j] = 0
                else:
                    height[j] += 1
            cur = self.largestRectangleArea(height)
            if cur > maxArea:
                maxArea = cur
        return maxArea
        
    def largestRectangleArea(self, height):  
        height.append(0)  
        maxArea = 0  
        i = 0  
        index = []  
        while i < len(height):  
            if len(index) == 0 or height[index[-1]] <= height[i]:  
                index.append(i)  
                i += 1  
            else:  
                t = index.pop()  
                if len(index) == 0:  
                    maxArea = max(maxArea, height[t] * i)  
                else:  
                    maxArea = max(maxArea, height[t] * (i - 1 - index[-1]))  
        return maxArea