Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Brain activity: Pick a rectangle, with its height being "the height", what's the largest area you can extend?
The expansion can continue to go both directions centered with this rectangle, as long as the others are taller, until you meet the "ditches", which are the first ones shorter.
To accelerate the algorithm to at most O(NlgN), some tricks are needed for finding the "ditch" locations.

Notice that only shorter rectangles can "ditch" the expasion.

So the idea is: If the positions of all the shorter rectangles are known, and sorted in a set, then after is inserted the position of current rectangle, the "ditch" positions are the neighbors!

Considering the duplicate heights (different positions with the same height). Since same heights do not "ditch" each other, so the insertion of positions should occur after the "ditch" neighbors are found.

Step 1: Sort the rectangles by height, from short to tall (hist[]). Their original positions will be recorded in (index[]) in the order of (hist[]).
Step 2: Rectangles from low to high
                 Register height, (h) and current position, (pos)
                 Use this position find the neighbors in (index[]), (leftDitch) and (rightDitch)
                 Calculate the area with the height (h) * (rightDitch - leftDitch -1)
                 Push the (pos) into ditch set (index[])
                 Repeat step 2
Step 3: Find the max area calculated in Step 2. (Can be done O(N) time)


Barely passed the large test.

class Solution {
    struct HPOS{int h;int pos;HPOS(int a, int b):h(a),pos(b){}};
public:
friend    bool operator<(HPOS a, HPOS b){
        return a.h < b.h;
    }

    int largestRectangleArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int maxArea = 0;
        multiset<HPOS> hist;//height,pos
        for(int ii = 0; ii < height.size(); ++ii){
            hist.insert(HPOS(height[ii],ii));
        }
        set<int> index;//all the short height positions
        for(multiset<HPOS>::iterator it = hist.begin(); it != hist.end();){//from shortest to tallest
            multiset<HPOS>::iterator hBoundEnd = hist.equal_range(HPOS(it->h,it->pos)).second;
            //count how many with the same height
            //at least one, itself
            vector<int> equalIndex;//do not count same height positions
            for(; it != hBoundEnd; ++it){
                equalIndex.push_back(it->pos);
                pair<set<int>::iterator, set<int>::iterator> bound = index.equal_range(it->pos);
                //find the closest left ditch and right ditch
                //bound.first is it->pos itself
             int leftDitch = 0;
          int rightDitch = height.size() - 1;
                if (bound.first != index.begin()){
                    advance(bound.first,-1);
                    leftDitch = *bound.first + 1;
                }
                if (bound.second != index.end()) rightDitch = *bound.second-1;
                int area = (rightDitch-leftDitch+1) * it->h;
                if (maxArea < area) maxArea = area;
            }
            for(int ii = 0; ii < equalIndex.size(); ++ii){
                index.insert(equalIndex[ii]);
            }
        }
        return maxArea;
    }
};