Largest Rectangle in Histogram

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.

-------------------------------------- thinking ------------------------------------------

-------------------------------------- codes ----------------------------------------------
   class Solution {
   public:
       int largestRectangleArea(vector<int> &height) {
           stack<int> stk;
           int max = 0;
           int area;
           for (int i = 0; i < height.size(); i++) {
               if (stk.size() == 0 || height[i] > height[stk.top()]) {
                   stk.push(i);
               } else {
                   while (stk.size() && height[stk.top()] >= height[i]) {
                       int ind = stk.top();
                       stk.pop();
                       if (stk.size() == 0) {
                           //bug here (i instead of (i-1))
                           area = height[ind] * i;
                       } else {
                           //bug here (i - stk.top() - 1 instead of i-stk.top())
                           area = height[ind] * (i - stk.top() - 1);
                       }
                       max = max > area? max : area;
                   }
                   stk.push(i);
               }
           }
           while (stk.size()) {
               int ind = stk.top();
               stk.pop();
               if (stk.size() == 0) {
                   area = height[ind] * height.size();
               } else {
                    //bug here -> instead of (cur_ind - stk.top() - 1) we should do (height.size() - stk.top() - 1)
                   area = height[ind] * (height.size() - stk.top() - 1);
               }
               max = max>area?max:area;
           }
           return max;
       }

   };