Largest Rectangle in Histogram Solutions in C++

// Source : https://oj.leetcode.com/problems/largest-rectangle-in-histogram/
// Author : Hao Chen
// Date   : 2014-07-20



#include <iostream>
#include <vector>
using namespace std;

//Time Limit Exceeded
int largestRectangleArea_01(vector<int>& heights) {
    if (heights.size() == 0) return 0;

    // idx of the first bar in the left or right that is lower than current bar
    vector<int> left(heights.size()); 
    vector<int> right(heights.size());

    right[heights.size() - 1] = heights.size();
    left[0] = -1;

    for (int i = 1; i < heights.size(); i++) {
        int l = i - 1;
        while (l >= 0 && heights[l] >= heights[i]) {
            l--;
        }
        left[i] = l;
    }

    for (int i = heights.size() - 2; i >= 0; i--) {
        int r = i + 1;
        while (r < heights.size() && heights[r] >= heights[i]) {
            r++;
        }
        right[i] = r;
    }

    int maxArea = 0;
    for (int i = 0; i < heights.size(); i++) {
        maxArea = max(maxArea, heights[i] * (right[i] - left[i] - 1));
    }

    return maxArea;        

}


// As we know, the area = width * height
// For every bar, the 'height' is determined by the loweset bar.
//
// 1) We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. 
// 2) A bar is popped from stack when a bar of smaller height is seen. 
// 3) When a bar is popped, we calculate the area with the popped bar as smallest bar. 
// 4) How do we get left and right indexes of the popped bar – 
//    the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. 
//
//
// In other word, the stack only stores the incresing bars, let's see some example  
//
// Example 1
// ---------
// height = [1,2,3,4]
//
//    stack[] = [ 0, 1, 2, 3 ], i=4
//
//    1) pop 3,  area = height[3] * 1 = 4
//    2) pop 2,  area = height[2] * 2 = 4
//    3) pop 1,  area = height[1] * 3 = 6
//    4) pop 0,  area = height[0] * 4 = 4
//
//
// Example 2
// ---------
// height = [2,1,2]
//
//    stack[] = [ 0 ], i=1
//    1) pop 0,  area = height[0] * 1 = 2
//
//    stack[] = [ 1,2 ], i=3, meet the end
//    1) pop 2,  area = height[2] * 1 = 2
//    2) pop 1,  area = height[1] * 3 = 3
//
//
// Example 3
// ---------
// height =  [4,2,0,3,2,5]  
//
//    stack[] = [ 0 ], i=1, height[1] goes down
//    1) pop 0,  area = height[0] * 1 = 4
//
//    stack[] = [ 1 ], i=2, height[2] goes down
//    1) pop 1,  area = height[1] * 2 = 4 // <- how do we know the left?
//                                              start from the 0 ?? 
//
//    stack[] = [ 2, 3 ], i=4, height[4] goes down
//    1) pop 3,  area = height[3] * 1 = 3
//    2) pop 2,  area = height[2] * ? = 0 // <- how do we know the left? 
//                                              start from the 0 ??
//
//    stack[] = [ 2,4,5 ], i=6,  meet the end
//    1) pop 5,  area = height[5] * 1 = 5
//    2) pop 4,  area = height[4] * 3 = 6 // <- how do we know the left?
//                                              need check the previous item.
//    3) pop 2,  area = height[2] * ? = 4 // <- how do we know the left?
//                                              start from the 0 ??
//
//    so, we can see, when the stack pop the top, the area formular is 
//
//          height[stack_pop] *  i - stack[current_top] - 1,   if stack is not empty
//          height[stack_pop] *  i,                            if stack is empty
//
int largestRectangleArea(vector<int> &height) {
    if (height.size()<=0) return 0;
    //Create an empty stack.
    vector<int> stack;
    //add a flag as a trigger if the end bar is met, and need to check the stack is empty of not .
    height.push_back(0);
    int maxArea = 0;
    for(int i=0; i<height.size(); i++){
        //If stack is empty or height[i] is higher than the bar at top of stack, then push ‘i’ to stack.
        if ( stack.size()<=0 || height[i] >= height[stack.back()] ) {
            stack.push_back(i);
            continue;
        }
        //If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. 
        //Let the removed bar be height[top]. Calculate area of rectangle with height[top] as smallest bar. 
        //For height[top], the ‘left index’ is previous (previous to top) item in stack and ‘right index’ is ‘i’ (current index).
        int topIdx = stack.back();
        stack.pop_back();
        int area = height[topIdx] * (stack.size()==0 ? i : i - stack.back() - 1 );
        if ( area > maxArea ) {
            maxArea = area;
        }
        //one more time. Because the stack might still have item.
        i--;
    }

    return maxArea;
}

void printArray(vector<int> &v)
{
    cout << "{";
    for(int i=0; i<v.size(); i++) {
        cout << " " << v[i];
    }
    cout << "}" << endl;
}
void test(int a[], int n)
{
    vector<int> v(a, a + n);
    printArray(v);
    cout << largestRectangleArea(v) << endl;
}

int main()
{
#define TEST(a) test(a, sizeof(a)/sizeof(int))

    int a0[] = {2,1,3,1};
    TEST(a0);
    int a1[] = {2,1,5,6,2,3};
    TEST(a1);

    return 0;
}

/*int main()
  {
  int a[] = {2,1,5,6,2,3};
  vector<int> v(a, a + sizeof(a)/sizeof(int));
  printArray(v);
  cout << largestRectangleArea(v) << endl;
  return 0;
  }*/

#include <vector>
using std::vector;
#include <stack>
using std::stack;
#include <algorithm>
using std::max;

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int max_area = 0, i = 0, size = height.size();
        for (stack<int> stk; i<size || !stk.empty(); )
            if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++);
            else {
                int tp = stk.top(); stk.pop();
                max_area = max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1));
            }
        return max_area;
    }
};

/// Source : https://leetcode.com/problems/largest-rectangle-in-histogram/
/// Author : liuyubobobo
/// Time   : 2020-05-13

#include <iostream>
#include <vector>

using namespace std;


/// Divide and Conquer + Segment Tree
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class SegmentTree{

private:
    int n;
    vector<int> data, tree;

public:
    SegmentTree(const vector<int>& data): data(data.begin(), data.end()), n(data.size()), tree(4*n, 0){
        buildSegTree(0, 0, n - 1);
    }

    int query(int l, int r){
        return query(0, 0, n - 1, l, r);
    }

private:
    void buildSegTree(int treeID, int l, int r){

        if(l == r){
            tree[treeID] = l;
            return;
        }

        int mid = (l + r) / 2;
        buildSegTree(treeID * 2 + 1, l, mid);
        buildSegTree(treeID * 2 + 2, mid + 1, r);
        tree[treeID] = data[tree[treeID * 2 + 1]] < data[tree[treeID * 2 + 2]] ? tree[treeID * 2 + 1] : tree[treeID * 2 + 2];
        return;
    }

    int query(int treeID, int l, int r, int ql, int qr){

        if(ql == l && qr == r)
            return tree[treeID];

        int mid = (l + r) / 2;
        if(qr <= mid) return query(treeID * 2 + 1, l, mid, ql, qr);
        else if(ql > mid) return query(treeID * 2 + 2, mid + 1, r, ql, qr);

        int resl = query(treeID * 2 + 1, l, mid, ql, mid);
        int resr = query(treeID * 2 + 2, mid + 1, r, mid + 1, qr);
        return data[resl] < data[resr] ? resl : resr;
    }
};

class Solution {

private:
    int n;

public:
    int largestRectangleArea(vector<int>& heights) {

        n = heights.size();
        if(!n) return 0;

        SegmentTree tree(heights);
        return largest(heights, 0, n - 1, tree);
    }

private:
    int largest(const vector<int>& heights, int l, int r, SegmentTree& tree){

        if(l > r) return 0;
        if(l == r) return heights[l];

        int min_index = tree.query(l, r);
        int res = largest(heights, l, min_index - 1, tree);
        res = max(res, largest(heights, min_index + 1, r, tree));
        res = max(res, heights[min_index] * (r - l + 1));
        return res;
    }
};


int main() {

    vector<int> heights = {2,1,5,6,2,3};
    cout << Solution().largestRectangleArea(heights) << endl;
    // 10

    return 0;
}

/// Source : https://leetcode.com/problems/largest-rectangle-in-histogram/
/// Author : liuyubobobo
/// Time   : 2020-05-13

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

using namespace std;


/// Monotone Stack
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int largestRectangleArea(vector<int>& heights) {

        int n = heights.size();
        if(!n) return 0;

        stack<int> stack;
        int res = 0;
        for(int i = 0; i < n; i ++){
            while(!stack.empty() && heights[i] < heights[stack.top()]){
                int x = stack.top();
                res = max(res, heights[x]);
                stack.pop();
                if(!stack.empty()) res = max(res, heights[x] * (i - 1 - (stack.top() + 1) + 1));
                else res = max(res, heights[x] * i);
            }
            stack.push(i);
        }

        if(!stack.empty()){
            int r = stack.top();
            while(!stack.empty()){
                int x = stack.top();
                stack.pop();
                res = max(res, heights[x]);

                if(!stack.empty()) res = max(res, heights[x] * (r - (stack.top() + 1) + 1));
                else res = max(res, heights[x] * n);
            }
        }
        return res;
    }
};


int main() {

    vector<int> heights1 = {2,1,5,6,2,3};
    cout << Solution().largestRectangleArea(heights1) << endl;
    // 10

    vector<int> heights2 = {2,1,2};
    cout << Solution().largestRectangleArea(heights2) << endl;
    // 3

    vector<int> heights3 = {0, 9};
    cout << Solution().largestRectangleArea(heights3) << endl;
    // 9

    vector<int> heights4 = {5, 4, 1, 2};
    cout << Solution().largestRectangleArea(heights4) << endl;
    // 8

    vector<int> heights5 = {1, 2, 3, 4, 5};
    cout << Solution().largestRectangleArea(heights5) << endl;
    // 9

    vector<int> heights6 = {4, 2, 0, 3, 2, 5};
    cout << Solution().largestRectangleArea(heights6) << endl;
    // 6

    return 0;
}

/// Source : https://leetcode.com/problems/largest-rectangle-in-histogram/
/// Author : liuyubobobo
/// Time   : 2020-05-14

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

using namespace std;


/// Monotone Stack with sentinel to simplify the code
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int largestRectangleArea(vector<int>& heights) {

        if(!heights.size()) return 0;

        heights.insert(heights.begin(), 0);
        heights.push_back(0);

        stack<int> stack;
        int res = 0;
        for(int i = 0; i < heights.size(); i ++){
            while(!stack.empty() && heights[i] < heights[stack.top()]){
                int x = stack.top();
                res = max(res, heights[x]);
                stack.pop();
                if(!stack.empty()) res = max(res, heights[x] * (i - 1 - (stack.top() + 1) + 1));
                else res = max(res, heights[x] * i);
            }
            stack.push(i);
        }
        return res;
    }
};


int main() {

    vector<int> heights1 = {2,1,5,6,2,3};
    cout << Solution().largestRectangleArea(heights1) << endl;
    // 10

    vector<int> heights2 = {2,1,2};
    cout << Solution().largestRectangleArea(heights2) << endl;
    // 3

    vector<int> heights3 = {0, 9};
    cout << Solution().largestRectangleArea(heights3) << endl;
    // 9

    vector<int> heights4 = {5, 4, 1, 2};
    cout << Solution().largestRectangleArea(heights4) << endl;
    // 8

    vector<int> heights5 = {1, 2, 3, 4, 5};
    cout << Solution().largestRectangleArea(heights5) << endl;
    // 9

    vector<int> heights6 = {4, 2, 0, 3, 2, 5};
    cout << Solution().largestRectangleArea(heights6) << endl;
    // 6

    return 0;
}

/// Source : https://leetcode.com/problems/largest-rectangle-in-histogram/
/// Author : liuyubobobo
/// Time   : 2020-05-20

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

using namespace std;


/// A very cool idea, using a dp-like thoughts
/// See here for details: https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28902/5ms-O(n)-Java-solution-explained-(beats-96)
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int largestRectangleArea(vector<int>& heights) {

        int n = heights.size();
        if(!n) return 0;

        heights.insert(heights.begin(), INT_MAX);
        heights.push_back(INT_MAX);

        vector<int> left(n + 2), right(n + 2);
        left[0] = 0;
        for(int i = 1; i <= n; i ++){
            int p = i - 1;
            while(p > 0 && heights[i] <= heights[p])
                p = left[p];
            left[i] = p;
        }
//        for(int e: left) cout << e << " "; cout << endl;

        right[n + 1] = n + 1;
        for(int i = n; i >= 1; i --){
            int p = i + 1;
            while(p < n + 1 && heights[i] <= heights[p])
                p = right[p];
            right[i] = p;
        }
//        for(int e: right) cout << e << " "; cout << endl;

        int res = 0;
        for(int i = 1; i <= n; i ++)
            res = max(res, heights[i] * (right[i] - left[i] - 1));
        return res;
    }
};


int main() {

    vector<int> heights1 = {2,1,5,6,2,3};
    cout << Solution().largestRectangleArea(heights1) << endl;
    // 10

    vector<int> heights2 = {2,1,2};
    cout << Solution().largestRectangleArea(heights2) << endl;
    // 3

    vector<int> heights3 = {0, 9};
    cout << Solution().largestRectangleArea(heights3) << endl;
    // 9

    vector<int> heights4 = {5, 4, 1, 2};
    cout << Solution().largestRectangleArea(heights4) << endl;
    // 8

    vector<int> heights5 = {1, 2, 3, 4, 5};
    cout << Solution().largestRectangleArea(heights5) << endl;
    // 9

    vector<int> heights6 = {4, 2, 0, 3, 2, 5};
    cout << Solution().largestRectangleArea(heights6) << endl;
    // 6

    return 0;
}