LeetCode Largest Rectangle in Histogram

class SegmentTree {
    private:
        int *mem;
        int *idx;
        int capacity;
        int storage_size;

    private:
        void init_level_update() {
            int k = capacity - 1;
            while (--k >= 0) {
                int L = (k<<1) + 1;
                int R = L + 1;
                if (mem[L] < mem[R]) {
                    mem[k] = mem[L];
                    idx[k] = idx[L];
                } else {
                    mem[k] = mem[R];
                    idx[k] = idx[R];
                }
            }
        }

        pair<int, int> query(int a, int b, int idx, int L, int R) {
            if (b <= L || a >= R) return make_pair(INT_MAX, -1);
            if (a <= L && R <= b) return make_pair(mem[idx], this->idx[idx]);

            pair<int, int> ml = query(a, b, (idx<<1) + 1, L, (L+R)/2);
            pair<int, int> mr = query(a, b, (idx<<1) + 2, (L+R)/2, R);
            if (ml.second == -1) return mr;
            if (mr.second == -1) return ml;
            return ml.first < mr.first ? ml : mr;
        }

        void init_mem(int _capacity) {
            if (_capacity <= 0) {
                capacity = 0;
                return;
            }
            int n = 1;
            while (n < _capacity) n<<=1;
            capacity = n;
            storage_size = capacity * 2 - 1;
            mem = new int[storage_size];
            idx = new int[storage_size];
            
            int k = 0;
            while (k < storage_size) mem[k++] = INT_MAX;
            k = capacity - 1;
            int i = 0;
            while (k < storage_size) idx[k++] = i++;
        }
    public:
        SegmentTree(int _capacity) {
            init_mem(_capacity);
        }
        SegmentTree(vector<int>::iterator begin, vector<int>::iterator end) {
            capacity = end - begin;
            init_mem(capacity);

            int k = capacity - 1;
            vector<int>::iterator iter = begin;
            while (iter != end) mem[k++] = *iter++;

            init_level_update();
        }

        ~SegmentTree() {
            delete[] mem;
            delete[] idx;
        }

        // update value in original data index
        void update(int index, int val) {
            if (index >= capacity || idx < 0) return;
            int k = index + capacity - 1; // internal storage index
            mem[k] = val;
            while (k > 0) {
                k = (k - 1) >> 1;
                int L = (k << 1) + 1;
                int R = L + 1;
                if (mem[L] < mem[R]) {
                    mem[k] = mem[L];
                    idx[k] = idx[L];
                } else {
                    mem[k] = mem[R];
                    idx[k] = idx[R];
                }
            }
        }

        // retrive the min value in index range [a, b)
        pair<int, int> query(int a, int b) {
            return query(a, b, 0, 0, capacity);
        }

        void print_mem(const char* msg) {
            cout<<msg<<endl;
            for (int i=0; i<(capacity*2-1); i++) {
                cout<<mem[i]<<" ";
            }
            
            for (int i=0; i<capacity * 2 - 1; i++) {
                cout<<idx[i]<<",";
            }
            cout<<endl;
        }
};

class Solution {
private:
    SegmentTree* seg_tree;
public:
    // this brute-force method will case TLE
    int bf_largestRectangleArea(vector<int> &height) {
        vector<bool> visited(height.size(), false);
        int len = height.size();
        int max_area = 0;
        for (int i=0; i<len; i++) {
            int ch = height[i];
            int range = 1;
            if (visited[i]) continue;
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] < ch) break;
                if (height[j] == ch) visited[j] = true;
                range++;
            }
            for (int j = i + 1; j < len; j++) {
                if (height[j] < ch) break;
                if (height[j] == ch) visited[j] = true;
                range++;
            }
            if (range * ch > max_area) max_area = range * ch;
        }
        return max_area;
    }
    
    int largestRectangleArea(vector<int> &height) {
        seg_tree = new SegmentTree(height.begin(), height.end());
        int maxarea = dfs(0, height.size());
        delete seg_tree;
        return maxarea;
    }
    
    int dfs(int L, int R) {
        int ret = 0;
        if (L >= R) return ret;
        pair<int, int> res = seg_tree->query(L, R);
        ret = (R - L) * res.first;
        int ml = dfs(L, res.second);
        int mr = dfs(res.second + 1, R);
        return max(ret, max(ml, mr));
    }
};

人艰不拆，趁机学习了一下线段树，180+ms，数据多的情况下（如大量连续递增序列）有可能造成栈溢出

找到一个巧妙的O(n)解法

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int len = height.size();
        if (len == 0) return 0;
        int maxarea = height[0], area;
        vector<int> stack;
        int pos = 0, idx;
        while (pos<len) {
            if (stack.empty() || height[stack.back()] <= height[pos]) {
                stack.push_back(pos++);
            } else {
                idx = stack.back();
                stack.pop_back();
                area = height[idx] * (stack.empty() ? pos : pos - stack.back() - 1);
                if (area > maxarea) maxarea = area;
            }
        }
        
        while (!stack.empty()) {
            idx = stack.back();
            stack.pop_back();
            area = height[idx] * (stack.empty() ? pos : pos - stack.back() - 1);
            if (maxarea < area) maxarea = area;
        }
        
        return maxarea;
    }
};

100+ms

后来看了zhuli哥的解法，感觉更自然一点，就是先求出两个数组L,R，他们存储了从位置i开始向左/右不小于height[i]的且中间不被隔断的最远的一条bar的索引值，求的过程中可以复用以前的结果，这样就比暴力的找两个端点高效很多，时间也是这几种方法里最快的。下面给出代码：

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int len = height.size();
        if (len == 0) return 0;
        int maxarea = 0;
        vector<int> L, R;
        L.resize(len), R.resize(len);
        for (int i=0; i<len; i++) {
            L[i] = i;
            while (L[i]-1 >= 0 && height[L[i]-1] >= height[i]) {
                L[i] = L[L[i] - 1];
            }
        }
        int area;
        for (int i=len-1; i>=0; i--) {
            R[i] = i;
            while (R[i]+1 <= len-1 && height[R[i]+1] >= height[i]) {
                R[i] = R[R[i] + 1];
            }
            area = (R[i] - L[i] + 1) * height[i];
            if (area > maxarea) maxarea = area;
        }
        return maxarea;
    }
};

60ms+

感觉关键还是怎么样去分解问题，把其中的效率瓶颈解决掉，另外简单最美

这回用下那个是用stack的版本的解法，似乎要好理解一些，同时也适用于很多类似的问题

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        height.push_back(0);
        int len = height.size();
        stack<int> pos;
        int maxarea = 0;
        for (int i=0; i<len; i++) {
            while (!pos.empty() && height[i] < height[pos.top()]) {
                int last = pos.top();
                pos.pop();
                
                int w = i - (pos.empty() ? -1 : pos.top()) - 1;
                int h = height[last];
                
                maxarea = max(w * h, maxarea);
            }
            pos.push(i);
        }
        return maxarea;
    }
};

参考：

　　http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/

　　http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

　　http://www.cnblogs.com/zhuli19901106/p/3568217.html

　　http://www.julyedu.com/course/index/category/algorithm.html