首页 > 动态规划 > 线性DP > LeetCode-Maximal Rectangle[动态规划]
2014
11-18

LeetCode-Maximal Rectangle[动态规划]

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.

标签: Array Hash Table Stack Dynamic Programming
分析

代码1

// LeetCode, Maximal Rectangle
// 时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty())  return 0;

        const int m = matrix.size();
        const int n = matrix[0].size();
        vector<int> H(n, 0);
        vector<int> L(n, 0);
        vector<int> R(n, n);

        int ret = 0;
        for (int i = 0; i < m; ++i) {
            int left = 0, right = n;
            // calculate L(i, j) from left to right
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    ++H[j];
                    L[j] = max(L[j], left);
                } else {
                    left = j+1;
                    H[j] = 0; L[j] = 0; R[j] = n;
                }
            }
            // calculate R(i, j) from right to left
            for (int j = n-1; j >= 0; --j) {
                if (matrix[i][j] == '1') {
                    R[j] = min(R[j], right);
                    ret = max(ret, H[j]*(R[j]-L[j]));
                } else {
                    right = j;
                }
            }
        }
        return ret;
    }
};

Java代码:

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int ans = 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int heights[] = new int[matrix[0].length];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(matrix[i][j] == '1')
                    heights[j] ++;
                else
                    heights[j] = 0;
            }
            int tmp = largestRectangleArea(heights);
            if(ans < tmp) ans = tmp;
        }

        return ans;
    }
    
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<Integer>();
		int i=0;
		int ans = 0;
		while(i < heights.length){
			if(stack.isEmpty() || heights[i] > heights[stack.peek()] ){
				stack.push(i++);
			}else{
				int start = stack.pop();
				int width = stack.isEmpty() ? i : i-stack.peek()-1 ;
				ans = Math.max(ans, heights[start] * width);
			}
		}
		
		while(!stack.isEmpty()){
			int start = stack.pop();
			int width = stack.isEmpty() ? heights.length : heights.length-stack.peek()-1 ;
			ans = Math.max(ans, heights[start] * width);
		}
		return ans;
    }
}

  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.