题目4---求直方图的最大矩形面积(2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

#include<iostream>
#include<vector>
#include<stack>
#include<set>

class CFuncTrace final 
{
public:
    explicit CFuncTrace(const std::string strFuncName)
    {
        m_funcName = strFuncName;
        std::cout << std::endl<<  m_funcName  <<" Begin"  <<std::endl;
    }
    ~CFuncTrace()
    {
        std::cout<<  std::endl << m_funcName << " End" << std::endl;
    }
private:
    std::string m_funcName;
};
/*
 `()`中标识当前计算的位置 `{}`标识已经计算的数据。`[]`标识所有的数。
[2]
[(2)]={IndexRange: [0,0]   Value:2 Counts: 1 Area:2}
[{2},1]
[{2},1,5]
[{2},1,5,6]
[{2},1,5,(6)]={IndexRange: [3,3]   Value:6 Counts: 1 Area:6}
[{2},1,(5),{6}]={IndexRange: [2,3]   Value:5 Counts: 2 Area:10}
[{2},1,{5},{6},2]
[{2},1,{5},{6},2,3]
[{2},1,{5},{6},2,(3)]={IndexRange: [5,5]   Value:3 Counts: 1 Area:3}
[{2},1,{5},{6},(2),{3}]={IndexRange: [2,5]   Value:2 Counts: 4 Area:8}
[{2},(1),{5},{6},{2},{3}]={IndexRange: [0,5]   Value:1 Counts: 6 Area:6}
 */
int CalcRectMax2(std::vector int> valueVec)
{
    CFuncTrace fuc(__PRETTY_FUNCTION__);
    std::vector<int> innerVec;
    innerVec.insert(innerVec.end(),valueVec.begin(),valueVec.end());
    std::set int> indexSet;
    int maxArea=0;
    for(int index = 0; index <  valueVec.size();)
    {
        if(indexSet.empty() || valueVec[index] > valueVec[(*indexSet.rbegin())])
        {
            indexSet.insert(index);
            index++;
        }
        else
        {
            int count = 0;
            int leftIndex = *(indexSet.rbegin());
            int area = valueVec[leftIndex]*(index-leftIndex);
            std::cout << "IndexRange: [" <<  leftIndex  << "," <<  index-1  "]   Value:"  <<  valueVec[leftIndex] <<   " Counts: "<<   (index-leftIndex) <<  " Area:"  << area <<  std::endl;
            if(area > maxArea)
            {
maxArea = area;
            }
            indexSet.erase(leftIndex);
        }    
    }

    int rightIndex = 0;
    while(!indexSet.empty())
    {
        int index = *indexSet.rbegin();
        int leftIndex = index;
        while(index >= 0)
        {
            if(valueVec[index] >= valueVec[*(indexSet.rbegin())])
            {
leftIndex = index;
index--;
            }
            else
            {
break;
            }
        }

        int area = valueVec[*(indexSet.rbegin())]*(valueVec.size()-leftIndex);
        std::cout <<  "IndexRange: [" <<  leftIndex  << ","<<   innerVec.size() <<  "]   Value:" <<   innerVec[*(indexSet.rbegin())] <<   " Counts: " <<  (innerVec.size()-leftIndex)  << " Area:"  << area <<  std::endl;
        if(area > maxArea)
        {
            maxArea = area;
        }
        indexSet.erase(*(indexSet.rbegin()));
    }
    return maxArea;
}


int main(int argc,char * argv[])
{
    std::vector <int> orgIntVec={2,1,5,6,2,3};
    std::cout <<  CalcRectMax2(orgIntVec) <<  std::endl;
    return 0;
}