LeetCode 84. Largest Rectangle in Histogram调试模板-wowAC

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

image.png

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

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 string_to_int(const string &s) {
    return atoi(s.c_str());
}

vector<string> 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));
    return v;
}

vector<int> parse_string(string line) {
    int i = 0, j = line.length()-1;
    while(i<line.length() && line[i]!= '[') i++;
    while(j>=0 && line[j]!=']') j--;
    line = line.substr(i+1, j-i-1);
    vector<int> res;
    vector<string> s= split_string(line, ",");
    for(int i=0; i<s.size(); i++) {
        res.push_back(string_to_int(s[i]));
    }
    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)) {
        //cout<<line<<endl;
        if(line == "") continue;
        vector<int> input = parse_string(line);

        cout<<"case"<<kase++<<": "<<endl;
        cout<<solu.largestRectangleArea(input)<<endl;
    }
    return 0;
}

发表评论

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