[LeetCode] Largest Rectangle in Histogram-白红宇

has a very neat code, which is rewritten below using stack since the push and pop operations of it are O(1) time, while the pop_back and push_back of vector tend to be more time-consuming. This is also verified by the running time of the code on the OJ: stack version is generally 4ms to 8ms faster than vector version.

1 class Solution { 2 public: 3     int largestRectangleArea(vector
     
      & height) { 4         height.push_back(0); 5         int n = height.size(), area = 0; 6         stack
      
        indexes; 7         for (int i = 0; i < n; i++) { 8             while (!indexes.empty() && height[indexes.top()] > height[i]) { 9                 int h = height[indexes.top()]; indexes.pop();10                 int l = indexes.empty() ? -1 : indexes.top();11                 area = max(area, h * (i - l - 1));12             }13             indexes.push(i);14         }15         return area; 16     }17 };

Moreover, it would be better to keep height unmodified. So we loop for n + 1 times and manually set the h = 0 when i == n. The code is as follows.

1 class Solution { 2 public: 3     int largestRectangleArea(vector
     
      & height) { 4         int n = height.size(), area = 0, h, l; 5         stack
      
        indexes; 6         for (int i = 0; i <= n; i++) { 7             while (i == n || (!indexes.empty() && height[indexes.top()] > height[i])) { 8                 if (i == n && indexes.empty()) h = 0, i++; 9                 else h = height[indexes.top()], indexes.pop();          10                 l = indexes.empty() ? -1 : indexes.top();11                 area = max(area, h * (i - l - 1));12             }13             indexes.push(i);14         }15         return area;16     }17 };