LeetCode 85. Maximal Rectangle调试模板-wowAC

此代码为了方便大家调试用,使用的时候直接用自己的Solution类覆盖代码中的类,程序的输入文件路径默认在桌面的data_in.txt,使用的时候直接将LeetCode的case复制进文件即可。如下图所示。

image.png


#include <iostream>
#include <fstream>
#include <string.h>
#include <cstdlib>
#include <vector>
#include <stack>

using namespace std;

/***************改成自己的代码****************/
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> st; //栈 用于存储下标
        vector<int> L(heights.size());  //L[i]表示i左边距离i最近的heights小于heights[i]的位置
        vector<int> R(heights.size());  //R[i]表示i右边距离i最近的heights小于heights[i]的位置
        for(int i=0; i<heights.size(); i++) {
            while(!st.empty() && heights[st[st.size()-1]]>=heights[i])
                st.pop_back();
            if(st.empty()) L[i] = -1;
            else L[i] = st[st.size()-1];
            st.push_back(i);
        }
        st.clear();

        for(int i=heights.size()-1; i>=0; i--) {
            while(!st.empty() && heights[st[st.size()-1]]>=heights[i])
                st.pop_back();
            if(st.empty()) R[i] = heights.size();
            else R[i] = st[st.size()-1];
            st.push_back(i);
        }
        st.clear();

        int res = 0;
        for(int i=0; i<heights.size(); i++) {
            res = max(res, heights[i]*(R[i]-(L[i]+1)));
        }
        return res;
    }
    int maximalRectangle(vector<vector<char> >& matrix) {
        if(matrix.size()==0) return 0;  //空矩阵
        vector<int> heights(matrix[0].size());
        int res = 0;
        for(int i=0; i<matrix.size(); i++) {
            for(int j=0; j<matrix[i].size(); j++)
                if(matrix[i][j] == '0') heights[j] = 0;
                else heights[j] += 1;
            res = max(res, largestRectangleArea(heights));
        }
        return res;
    }
};
/***************到此为止****************/


/***************不要修改这些代码****************/
//假设字符串长度不超过100000
int p[100000];

void split_string(const string& s, const string& c, vector<string> &v){
    string::size_type pos1, pos2;
    pos2 = s.find(c);
    pos1 = 0;
    while(string::npos != pos2){
        v.push_back(s.substr(pos1, pos2-pos1));

        pos1 = pos2 + c.size();
        pos2 = s.find(c, pos1);
    }
    if(pos1 != s.length())
        v.push_back(s.substr(pos1));
}

void init(string &line) {
    stack<int> st;
    for(int i=0; i<line.length(); i++) {
        if(line[i]!='[' && line[i]!=']') continue;
        if(line[i]=='[') st.push(i);
        else if(line[i]==']'){
            if(st.empty()) {
                cout<<"请输入正确的case"<<endl;
                exit(1);
            }else {
                p[st.top()] = i;
                p[i] = st.top();
                st.pop();
            }
        }
    }
    if(!st.empty()) {
        cout<<"请输入正确的case"<<endl;
        exit(1);
    }
}

vector<char> get_1Darray(string &line, int s, int e) {
    vector<char> res;
    while(s<=e && line[s]==' ') s++;
    if(s==e+1 || line[s]!='[') return res;
    e = p[s];
    string temp = line.substr(s+1, e-s-1);
    vector<string> v;
    split_string(temp, ",", v);
    for(int i=0; i<v.size(); i++) {
        res.push_back(v[i][1]);
        //cout<<v[i][1]<<" ";
    }
    //cout<<endl;
    return res;
}

vector<vector<char> >get_2Darray(string &line, int s, int e) {
    vector<vector<char> > res;
    while(s<=e && line[s]==' ') s++;
    if(s==e+1 || line[s]!='[') return res;
    int s1 = s+1;
    while(1) {
        while(s1<=e && line[s1]!='[') s1++;
        if(s1 == e+1) break;
        res.push_back(get_1Darray(line, s1, p[s1]));
        //cout<<res[res.size()-1].size()<<endl;
        s1 = p[s1] + 1;
    }
    return res;
}

/***************完毕****************/


int main()
{
    //改成自己的输入路径,注意用双斜杠分割 默认输入文件为桌面的data_in.txt
    fstream fin("C:\\Users\\xingxing\\Desktop\\data_in.txt");
    string line;
    Solution solu;
    int kase = 1;
    while(getline(fin, line)) {
        if(line == "") continue;
        init(line);
        vector<vector<char> > res = get_2Darray(line, 0, line.length()-1);
        cout<<"case"<<kase++<<": "<<endl;
        cout<<solu.maximalRectangle(res)<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注