【leetcode #84 #85】Maximal Rectangle

很简单，很有趣的一类题，好像在CF上出现过。。不太记得了

题意是给你N个1*N的矩形排列，要你框一个框，使得框出来的面积最大，就像这样：

也就是说，一个高度，他要向后扩展的条件是，它后面的所有矩形高度不小于它。

考虑一种最简单的情况，若整个矩形阵是升序的，那么显然 ans = max(ans,h[i] * (n - i));

若序列不是升序的，那么对于任意位置的矩形，考虑仅向右拓展的情况，它前面的矩形只有小于它的高度的部分，以及它后面的矩形只有大于等于它，才能将这个矩形完整包括在内，如上右图的(5,6)，对于5来说，6只有5的部分才有用。那么我们只要把整个序列强行变成升序的就好了。

这里可以利用栈来实现，当h[i] >= height.top()时，压栈

当h[i] < height.top()时，弹栈，直到满足h[i] >= height.top()时，压栈，再将与弹栈数量相同的h[i]压栈

首先可以肯定，我们构造的栈一定是升序的，那么如上图，当我们构造到

(1,1,5,6)(第一个1因为上述步骤压入)，当2来到时，我们需要把(5,6)弹出

在弹出的过程中万一有最优解呢？

所以我们需要记录弹出时能够构造的最大矩形，显然，也应该是ans = max(ans,height.top()*cnt)，这里的cnt指弹栈数量

比如6弹出，应该记录1*6,然后5弹出，cnt++,记录2*5

当height.top()==1时，将3个2压栈，至此，(1,1,6,5)->(1,1,2,2,2)

所以整个流程是这样的：

2来到->(2)

-> 1来到 -> 2弹出，将两个1压入 -> (1,1)  //记录了2*1

-> 5来到 -> (1,1,5)

-> 6来到 -> (1,1,5,6)

-> 2来到 -> 6,5弹栈 -> 3个2压入 ->(1,1,2,2,2)  //记录了6*1 5*2

-> 3来到 -> (1,1,2,2,2,3)

再按推出的升序的ans公式扫一遍即可~

我觉得单调栈也能做，反正就是利用单调性做文章就行了

code：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int>hei;
    int ans = 0;
    for (int i = 0; i < heights.size(); ++i) {
        if (hei.empty() || hei.top() <= heights[i]) {
            hei.push(heights[i]);
        }
        else {
            int len = 1;
            while (!hei.empty() && hei.top() > heights[i]) {
                ans = max(ans, len*hei.top());
                hei.pop();
                len++;
            }
            while(len--) hei.push(heights[i]);
        }
    }
    int len = 1;
    while (!hei.empty()) {
        ans = max(ans, hei.top()*len);
        //cout << hei.top() << endl;
        hei.pop();
        len++;
    }
    return ans;
    }
};

然后#85 给你一个二维矩阵，要框出其中最大的全1矩形

只要知道从上往下看，假如有0就代表断了

简单来说就是如果当前这一行的这个位置是0，那么height[i]=0，不是0，就height[i]++;

然后用上面的代码跑N次就行啦

code：

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
       vector<int>height;
       int ans = 0;
       for(int i = 0; i < matrix.size(); ++i){
            for(int j = 0; j < matrix[i].size(); ++j){
                if(i == 0){
                    if(matrix[i][j] == '0') height.push_back(0);
                    else height.push_back(1);
                }
                else{
                    if(matrix[i][j] == '0') height[j] = 0;
                    else height[j] += 1;
                }
            }
            ans = max(ans,solve(height));
       }
       return ans;
    }
private:
    int solve(vector<int> heights) {
    stack<int>hei;
    int ans = 0;
    for (int i = 0; i < heights.size(); ++i) {
        if (hei.empty() || hei.top() <= heights[i]) {
            hei.push(heights[i]);
        }
        else {
            int len = 1;
            while (!hei.empty() && hei.top() > heights[i]) {
                ans = max(ans, len*hei.top());
                hei.pop();
                len++;
            }
            while (len--) hei.push(heights[i]);
        }
    }
    int len = 1;
    while (!hei.empty()) {
        ans = max(ans, hei.top()*len);
        //cout << hei.top() << endl;
        hei.pop();
        len++;
    }
    return ans;
}
};

其实和扫描线有点类似？