leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0084.cpp (836B)

      1 class Solution {
      2   public:
      3     int largestRectangleArea(vector<int> &heights) {
      4         int n = heights.size();
      5         vector<int> left(n), right(n);
      6         stack<int> st;
      7 
      8         for (int i = 0; i < n; i++) {
      9             left[i] = i;
     10             while (!st.empty() && heights[st.top()] >= heights[i]) {
     11                 left[i] = left[st.top()];
     12                 st.pop();
     13             };
     14             st.push(i);
     15         }
     16 
     17         for (int i = n - 1; i >= 0; i--) {
     18             right[i] = i;
     19             while (!st.empty() && heights[st.top()] >= heights[i]) {
     20                 right[i] = right[st.top()];
     21                 st.pop();
     22             };
     23             st.push(i);
     24         }
     25 
     26         int res = 0;
     27         for (int i = 0; i < n; i++)
     28             res = max(res, (right[i] - left[i] + 1) * heights[i]);
     29         return res;
     30     }
     31 };