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 =10unit.

Have you met this question in a real interview?

Yes

Example

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

use a small exmple to run the test.

line 15 condition should use height, not index

class Solution {

public:

/\*\*

 \* @param height: A list of integer

 \* @return: The area of largest rectangle in the histogram

 \*/

int largestRectangleArea\(vector<int> &height\) {

    // write your code here

    int largest = 0;

    stack<int> stk;

    for \(int i = 0; i <= height.size\(\); ++i\) {

        int curHeight = i == height.size\(\) ? 0 : height\[i\];

        while \(!stk.empty\(\) && curHeight <= height\[stk.top\(\)\]\) {

            int h = height\[stk.top\(\)\]; stk.pop\(\);

            int w = stk.empty\(\) ? i : i - stk.top\(\) - 1;

            int area = h \* w;

            largest = max\(area, largest\);

        }

        stk.push\(i\);

    }



    return largest;

}

};